#include<stdio.h>
#include<string.h>
#define DIM 1000000
FILE *fin=fopen("pinex.in","r");
FILE *fout=fopen("pinex.out","w");

int n,m,p,P[20],v[DIM],a,b,sol,d,x[20];

void ciur(){
int i,j;

    for(i = 2; i<=DIM-1; i++){
        if(v[i]==0){
            P[++p]=i;
            for(j = 2*i; j<=DIM-1; j+=i){
                v[j]=1;
            }
        }
    }
    P[p+1]=DIM+1;

}
int main(){

    ciur();

    fscanf(fin,"%d",&m);

    memset(v,0,sizeof(int));
    for(int t = 1; t<=m; t++){
        fscanf(fin,"%d %d",&a,&b);
        n=0;

        sol = 0;

        d=1;
        while( b!=1 && P[d]*P[d]<=b ){
            if( b%P[d]==0 ){
                while(b%P[d]==0){
                    b/=P[d];
                }
                x[++n]=P[d];
            }

            d++;
        }

        if(b!=1){
            x[++n]=b;
        }


        v[n+1]=0;

        int k;
        int nr=0;
        for(int i = 1; i <=n; i++){
            v[i]=0;
        }
        while(v[n+1]==0){
            k=1;
            while(v[k]==1){
                v[k]=0;
                k++;
                nr--;
            }
            v[k]=1;
            nr++;

            p=1;
            for(int i = 1; i<=n; i++){
                if(v[i]==1){
                    p*=x[i];
                }
            }
            if(v[n+1]==0){
                if(nr%2==1){
                    sol+=a/p;
                }
                else{
                    sol-=a/p;
                }
            }

        }

        fprintf(fout,"%d\n",a-sol);
        v[n+1]=0;
    }

return 0;
}