#include <bits/stdc++.h>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
bitset <1000000> c;
int q,nrprime[1000005];
long long i,j,a,n,b,subm[1000005],nr,numar,lim,nrfin,par,k,prod;
int main()
{
    for (i=2;i*i<=1000000;i++)
    {
        if (c[i]==0)
        {
            nrprime[++q]=i;
            for (j=i*i;j<=1000000;j+=i)
            {
                c[j]=1;
            }
        }
    }
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>a>>b;
        nr=0;
        for (j=1;j<=q;j++)
        {
            numar=0;
            while (b%nrprime[j]==0)
            {
                numar++;
                b=b/nrprime[j];
            }
            if (numar>0)
            {
                subm[++nr]=nrprime[j];
            }
        }
        if (b>1)
        {
            subm[++nr]=b;
        }
        lim=(1<<nr);
        nrfin=0;
        for (j=1;j<lim;j++)
        {
            par=0;
            prod=1;
            for (k=0;k<nr;k++)
            {
                if ((j&(1<<k))!=0)
                {
                    par++;
                    prod=prod*subm[k+1];
                }
            }
            if (par%2==0)
            {
                nrfin=nrfin-a/prod;
            }
            else
            {
                nrfin=nrfin+a/prod;
            }
        }
        g<<a-nrfin<<'\n';
    }
    return 0;
}