#include <bits/stdc++.h>
#define int long long
using namespace std;

ifstream fin ("pinex.in") ;
ofstream fout ("pinex.out") ;

const int mxrad = 1e6 ;

bool ciur[mxrad+5] ;
vector < int > divs ;
int answer = 0;

void backtrack ( int ind , int x , int n , int nrnr , int val )
{
    if ( ind == n )
    {
        if ( nrnr != 0 )
        {
            if ( nrnr % 2 == 1 )
                answer += x / val ;
            else
                answer -= x / val ;
        }
    }
    else
    {
        backtrack ( ind + 1 , x , n , nrnr , val ) ;
        if ( x / divs[ind] >= val )
            backtrack ( ind + 1 , x , n , nrnr + 1 , val * divs[ind] ) ;
    }
}

signed main()
{
    vector < int > prime ;
    for ( int i = 2 ; i <= mxrad ; i ++ )
    {
        if ( ciur[i] == 0 )
        {
            prime.push_back(i) ;
            for ( int j = i * 2 ; j <= mxrad ; j += i )
                ciur[j] = 1 ;
        }
    }

    int q ;
    fin >> q ;
    int lg = prime.size() ;
    while ( q -- )
    {
        divs.clear() ;
        int ind = 0 ;
        int a , b ;
        fin >> a >> b ;
        while ( ind < lg && prime[ind] * prime[ind] <= b && b != 1 )
        {
            if ( b % prime[ind] == 0 )
            {
                divs.push_back(prime[ind]) ;
                while ( b % prime[ind] == 0 )
                    b /= prime[ind] ;
            }
            ind ++ ;
        }
        if ( b != 1 )
            divs.push_back(b) ;
        int m = divs.size() ;
        answer = 0 ;
        backtrack ( 0 , a , m , 0 , 1 ) ;
        fout << a - answer ;
        fout << '\n' ;
    }

    return 0;
}