#include <stdio.h>
#include <stdlib.h>
#define MAXDIV 1000
#define MAXPRIM 500000

long long dvz[MAXDIV], ind, indpr;
char ciur[1000001];
long long prim[MAXPRIM];
int main(){
    long long m, a, b, i, j;
    long long rez=0;
    FILE*fi,*fo;
    fi=fopen("pinex.in","r");
    fo=fopen("pinex.out","w");
    fscanf(fi,"%lld", &m);

    ciur[0]=ciur[1]=1;
    for(i=2;i<=1000000;i++){
        if(ciur[i]==0){
            prim[indpr++]=i;
            for(j=i*i;j<=1000000;j+=i)
                ciur[j]=1;
        }
    }

    for(i=0;i<m;i++){
        fscanf(fi,"%lld%lld", &a, &b);
        rez=0;
        ind=0;
        long long d=0;
        while(prim[d]*prim[d]<=b){
            if(b%prim[d]==0){
                dvz[ind++]=prim[d];
                while(b%prim[d]==0)
                    b/=prim[d];
            }
            d++;
        }
        if(b>1)
            dvz[ind++]=b;
        for(j=1;j<(1<<ind);j++){
            long long k, cmmmc=1, nrbit=0;
            for(k=0;k<=ind;k++){
                if(j&(1<<k)){
                    nrbit++;
                    cmmmc*=dvz[k];
                }
            }
            if(nrbit%2==1)
                rez+=a/cmmmc;
            else
                rez-=a/cmmmc;
        }
        fprintf(fo,"%lld\n", a-rez);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}