#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const long long mx=1000000;
long long pr[100005],di[80],ex[80],nd,ans,a,b;
bool ci[mx+5];
void bck(long long x,long long re,long long sm)
{
    if(x<=nd)
    {
    bck(x+1,re*di[x],sm+1);
    bck(x+1,re,sm);
    }
    else
    {
        if(sm!=0)
        {
            if(sm%2==0)
                ans=ans+a/re;
            else
                ans=ans-a/re;
        }
    }
}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    long long n,i,j,sq,m;
    m=1;
    pr[1]=2;
    for(i=3;i<=mx;i=i+2)
        if(ci[i]==0)
    {
        m++;
        pr[m]=i;
        for(j=i*i;j<=mx;j=j+2*i)
            ci[j]=1;
    }
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a>>b;
        nd=0;
        for(j=1;j<=m;j++)
            if(b%pr[j]==0)
        {
            nd++;
            di[nd]=pr[j];
            while(b%pr[j]==0)
            {
                b=b/pr[j];
            }
        }

        if(b>1)
        {
            nd++;
            di[nd]=b;
        }
        ans=a;
    bck(1,1,0);
    cout<<ans<<"\n";
    }
    return 0;
}