#include<stdio.h>
int m,a,b,i,j,k,s,cj,prod,cati,d,cate,v[1001],ciur[1000001];
int main(){
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&m);
    d=2;
    while(d*d<1000000){
        for(i=2;i<=1000000/d;i++)
            ciur[i*d]=1;
        d++;
        while(ciur[d]==1)
            d++;
    }

    for(k=1;k<=m;k++){
        scanf("%d%d",&a,&b);
        //descompun in factori primi b
        d=2;
        cate=0;
        if(ciur[b]==1){
            while(b!=1){
                if(b%d==0){
                    cate++;
                    v[cate]=d;
                    while(b%d==0)
                        b/=d;
                }
                d++;
            }
        }
        else{
            cate++;
            v[cate]=b;
        }
        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;
}