#include<fstream>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
long long k,i,n,sum,s,d,j,prim[200001],hz[1000001],v[10001],w[10001],h,a,b,p;
int main(){
    in >> k;
    hz[1]=1;
    hz[0]=1;
    for( i = 1; i <= 1e6; i ++ ){
        if( hz[i] == 0 ){
            s++;
            prim[s] = i;
            for( j = i + i; j <= 1e6; j += i ){
                hz[j] = 1;
            }
        }
    }
    for( h = 1; h <= k; h ++ ){
        in >> a >> b;
        n = 0;
        sum = 0;
        for( i = 1; prim[i]*prim[i] <= b; i ++ ){
            if( b % prim[i] == 0 ){
                n++;
                v[n] = prim[i];
                while( b % prim[i] == 0 ){
                    b/=prim[i];
                }
            }
        }
        if( b > 1 ){
            n++;
            v[n] = b;
            b = 1;
        }
        for( i = 0; i <= n; i ++ ){
            w[i] = 0;
        }
        while( w[0] == 0 ){
            i = n;
            while( w[i] == 1 && i > 0 ){
                w[i] = 0;
                i--;
            }
            w[i] = 1;
            p = 1;
            d = 0;
            for( j = 1; j <= n; j ++ ){
                if( w[j] == 1 ){
                    p*=v[j];
                    d++;
                }
            }
            if( d % 2 == 1 ){
                sum-=a/p;
            }
            else{
                sum+=a/p;
            }

        }
        out<<sum<<"\n";
    }

    return 0;
}