#include <stdio.h>
#include <stdlib.h>
#define MAXDIV 100

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