#include<cstdio>
using namespace std;
int cnt=0,ciu[1000007],prim[100007];
void ciur()
{
    for(int i=2;i<=1000007;i++)
        if(ciu[i]==0)
    {
        cnt++;
        prim[cnt]=i;
        for(int j=i;j<=1000000;j+=i) ciu[j]=1;
    }
}
void pinex(long long a,long long b)
{
    int cnt2=0,val[1007];
    long long bb=b,aa=a;
    for(int i=1;i<=cnt;i++)
        if(bb%prim[i]==0)
    {
        cnt2++;
        val[cnt2]=prim[i];
        while(bb%prim[i]==0) bb/=prim[i];
    }
    if(bb!=1) {cnt2++;val[cnt2]=bb;}
    //printf("%d\n",cnt2);
    for(long i=1;i<=((1<<cnt2)-1);i++)
    {
        long long x=i,p=1;
        int cnt3=0;
        for(int j=1;j<=cnt2;j++)
        {
            if(x&1) {cnt3++;p*=val[j];}
            x>>=1;
        }
        if(cnt3&1) aa-=(a/p);
        else aa+=(a/p);
    }
    printf("%lld\n",aa);
}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        long long a,b;
        scanf("%lld %lld",&a,&b);
        pinex(a,b);
    }
}