#include<cstdio>
long long t,n,m,a,k,i,j,p,s,ss,q,nr,v[1001000],x[100100],y[100100];
FILE *f,*g;
int main(){
    f=fopen("pinex.in","r");
    g=fopen("pinex.out","w");
    fscanf(f,"%d",&t);
    v[1]=1;
    for(int ii=2;ii <= 1000000; ii++){
        if( v[ii] == 0 ){
            x[ ++nr ] = ii;
            for(int jj=ii+ii; jj<=1000000; jj+=ii){
                v[jj] = 1;
            }
        }
    }
    while(t--){
        fscanf(f,"%lld%lld",&n,&m);
        k=0;
        a=m;
        for( i = 1; i <= nr && x[i] <= a / x[i] ; i++ ){
            if( a % x[i] == 0 ){
                y[++k] = x[i];
                while( a % x[i] == 0 ){
                    a /= x[i];
                }
            }
        }
        if( a != 1){
            y[++k] = a;
        }
        p = ( 1LL << k ) - 1;
        s = n;
        for( i = 1; i <= p; i ++ ){
            q = 0;
            ss = 1;
            for( j = 0 ; j < k; j ++ ){
                if( ( ( i >> j ) & 1LL ) == 1LL ){
                    q++;
                    ss *= y[ j + 1 ];
                }
            }
            if( q % 2 )
                s -= n / ss;
            else
                s += n / ss;
        }
        fprintf(g,"%lld\n",s);
    }


    fclose(f);
    fclose(g);
    return 0;
}