#include <cstdio>
#include <bitset>
#include <vector>
#define pb push_back
using namespace std;
char const in [] = "pinex.in";
char const out [] = "pinex.out";
int const NM = 1e6 + 7;
typedef long long i64;
bitset <NM> v;
vector <i64> primes , primes2;
void ciur (int number)
{
    int i , j;
    for(i = 2 ; i * i <= number ; ++ i)
        if(! v [i])
            for(j = i * i ; j <= number ; j += i)
                v [j] = 1;
    for(i = 2 ; i <= number ; ++ i)
        if(! v [i])
            primes2 . pb (i);
}
bool isprime (i64 a)
{
    i64 f = 2;
    while(f * f <= a)
        if(f ++ % a == 0)
            return 0;
    return 1;

}
int main()
{
    FILE *cin , *cout;
    cin = fopen (in , "r");
    cout = fopen (out , "w");
    i64 t , a , b , i , j;
    fscanf (cin , "%lld" , &t);
    fscanf (cin , "\n");
    ciur (NM);
    for(i = 1 ; i <= t ; ++ i)
    {
        fscanf (cin , "%lld %lld \n" , &a , &b);
        primes . clear ();
        int f ;
        i64 b1 = b;
        int aa = primes2 . size ();
        for(f = 0 ; b1 != 1 && f < aa ; ++ f)
        {
            int c = primes2 [f];
            if(b1 % primes2 [f] == 0)
            {
                primes . pb (primes2 [f]);
                while(b1 % primes2 [f] == 0)
                    b1 /= primes2 [f];
            }
        }
        if(b1 > 1 && isprime (b1))
            primes . pb (b1);
        i64 sol = 0;
        int sz = primes . size () , ij , ij2;
        int u , u2 , terms ;
        i64 prod ;
        if(sz == 0)
            sol = 0;
        else
            for(u2 = 1 ; u2 < (1 << sz)  ; ++ u2)
            {
                terms = 0;
                prod = 1;
                bool p = 0;
                for(u = 0 ; (1 << u) <= u2 ; ++ u)
                    if((1 << u) & u2)
                    {
                        if(u < sz)
                            prod = 1LL * prod * primes [u] , ++ terms;
                    }
                if(terms % 2)
                    sol = 1LL * (sol + a / prod);
                else
                    sol = 1LL * (sol - a / prod);
            }
        sol = 1LL * (a - sol);
        fprintf(cout , "%lld\n" , sol);
    }
    fclose (cin);
    fclose (cout);
    return 0;
}