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

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];
            while(b%pr[i]==0)b/=pr[i]; }
        i++;
        if(b<MAX&&(p[b]==0))break;
    }
    if(b!=1)fact[++n]=b;
}

void multimi(long long a){
    int num=1<<n,p;
    long long s=0,d;
    for(int k=1;k<num;k++){
        d=1;
        p=0;
        for(int i=0;i<n;i++)
        if(k&(1<<i)){ d*=fact[i+1]; p++; }
    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);
        }
}