#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int c[100101], p[100001], pr[20], f[20];
int main()
{
    int i, j, nrp, n;
    long long a, b, prod, r, aux, x;
    for(i=2;i<=100101;i++)
    {
        if(c[i]==0)
        {
            for(j=i+i;j<=100101;j+=i)
            {
                c[j]=1;
            }
        }
    }
    nrp=0;
    for(i=2;i<=100101;i++)
    {
        if(c[i]==0)
        {
            nrp++;
            p[nrp]=i;
        }
    }
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        x=0;
        aux=b;
        for(j=1;j<=nrp&&p[j]*1LL*p[j]<=b;j++)
        {
            if(b%p[j]==0)
            {
                x++;
                pr[x]=p[j];
                while(aux%p[j]==0)
                {
                    aux/=p[j];
                }
            }
        }
        if(aux!=1)
        {
            x++;
            pr[x]=aux;
        }
        r=0;
        for(j=0;j<=x;j++)
        {
            f[j]=0;
        }
        f[x]=1;
        while(f[0]==0)
        {
            int nr=0;
            prod=1;
            for(j=1;j<=x;j++)
            {
                if(f[j]==1)
                {
                    prod*=pr[j];
                    nr++;
                }
            }
            if(nr%2==1)
            {
                r+=a/prod;
            }
            else
            {
                r-=a/prod;
            }
            j=x;
            while(f[j]==1)
            {
                f[j]=0;
                j--;
            }
            f[j]=1;
        }
        fout<<a-r<<"\n";
    }
    return 0;
}