#include <cstdio>
#define MAX 1000010
bool p[MAX];
int pr[78505],nr,fact[20],n,x[20];

void ciur(){
    int i=2;
    while(i<=1000){
        while(i<MAX&&p[i])i++;
        for(int j=i*i;j<MAX;j+=i)p[j]=1;
        i++;
    }
    for(int i=2;i<MAX;i++)
    if(p[i]==0)pr[++nr]=i;
}

void desc(long long b){
    int i=1;
    while(pr[i]*pr[i]<=b){
        if(b%pr[i]==0){
            fact[++n]=pr[i];
            x[n]=0;
            while(b%pr[i]==0)b/=pr[i]; }
        i++;
    }
    if(b!=1)fact[++n]=b;
}

void multimi(long long a){
    int p=0,i;
    long long s=0,d;
    x[n+1]=0; fact[n+1]=1;
    while(x[n+1]==0)
    {
        i=1;
        while(x[i]==1){ x[i]=0; d/=fact[i]; p--; i++; }
        if(x[n+1]==0){
        x[i]=1; p++; d*=fact[i];
        if(p%2==1)s+=a/d; else s-=a/d; }
    }
    printf("%lld\n",a-s);
}

int main(){
    int t;
    long long a,b;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
        scanf("%d",&t);
        while(t--){
            scanf("%lld %lld",&a,&b);
            n=0;
            desc(b);
           // for(int i=1;i<=n;i++)printf("%d ",fact[i]); printf("\n");
            multimi(a);
        }
}