#include<cstdio>
#include<bitset>
#include<vector>
using namespace std;
bitset<500001> bs;
vector<long long> pr,p;
long long sol,a,i,prod,m,b,j,nr,sign,n;
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%lld",&m);
    pr.push_back(2);
    for(i=1;i<=500000;i++)
    {
        if(!bs[i])
        {
            pr.push_back(2*i+1);
            for(j=i*i;j<=500000;j+=2*i+1) bs[j]=1;
        }
    }
    for(;m;--m)
    {
        scanf("%lld %lld",&a,&b);
        p.resize(0); sol=a;
        for(i=0;b>1&&pr[i]<=1000000;i++)
        {
            if(b%pr[i]==0) p.push_back(pr[i]);
            for(;b%pr[i]==0;b/=pr[i]);
        }
        if(b>1) p.push_back(b);
        n=p.size();
        for(i=1;i<(1LL<<n);i++)
        {
            prod=1; nr=0;
            for(j=0;j<n;j++)
            {
                if(i&(1LL<<j))
                {
                    prod=prod*p[j];
                    nr++;
                }
            }
            if(nr&1) sign=-1;
            else sign=1;
            sol=sol+sign*(a/prod);
        }
        printf("%lld\n",sol);
    }
    return 0;
}