#include<stdio.h>
int m,a,b,i,j,k,s,cj,prod,cati,d,cate,v[1001];
int main(){
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&m);
    for(k=1;k<=m;k++){
        scanf("%d%d",&a,&b);
        //descompun in factori primi b
        d=2;
        cate=0;
        while(b!=1){
            if(b%d==0){
                cate++;
                v[cate]=d;
                while(b%d==0)
                    b/=d;
            }
            d++;
        }
        s=0;
        for(j=1;j<(1<<cate);j++){
            cj=j;
            prod=1;
            cati=0;
            for(i=0;i<=30;i++){
                if(cj&(1<<i)){
                    cati++;
                    prod*=v[i+1];
                }
            }
            if(cati%2==1)
                s+=(a/prod);
            else
                s-=(a/prod);
        }
    printf("%d\n",a-s);
    }
return 0;
}