#include<stdio.h>
int v[100001];
long long a,b;
int subm(int nr){
    int ct=0,p=1,i,j,sf=0;
    for(j=1;j<(1<<nr);j++){
        for(i=0;i<=31;i++){
            if((j&(1<<i))!=0){
                p*=v[i+1];
                ct++;}
        }
        if(ct%2==1)
            sf+=a/p;
        else
            sf-=a/p;
        p=1;
        ct=0;}
    return sf;
    }
int main(){
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int cb,i,j,n,k=0,rez;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&a,&b);
        cb=b;
        for(j=2;j*j<=cb;j++){
            if(b%j==0){
                k++;
                v[k]=j;
                while(b%j==0)
                    b=b/j;
            }
        }
        if(b!=1){
            k++;
            v[k]=j+1; }
    rez=a-subm(k);
    k=0;
    printf("%d\n",rez);
    }
    return 0;
}