#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 <int> primes;
void ciur (int number)
{
    int i , j;
    for(i = 1 ; i * i <= number ; ++ i)
        if(! v [i])
            for(j = i * i ; j <= number ; j += i)
                v [j] = 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;
        f = 2;
        while(f * f <= b)
        {
            if(v [f] && b1 % f == 0)
            {
                primes . pb (f) ;
                while(! (b1 % f))
                    b1 /= f;
            }
            ++ f;
        }
        if(b1 != 1)
            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)
                        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;
}