#include <fstream>
using namespace std;
long long Q, a, b, i, j, dim, P[500001], divi[30], d, ok, aux1, aux2, pr, nr, sol, val;
bool p[1000001];
bool sub[21];
int main()
{
    ifstream fin ("pinex.in");
    ofstream fout ("pinex.out");
    fin>>Q;
    p[1]=1;
    for (i=2; i<=1000000; i++)
        if (p[i]==0)
            for (j=2*i; j<=1000000; j+=i)
                p[j]=1;
    for (i=1; i<=1000000; i++)
        if (p[i]==0)
            P[++dim]=i;
    aux1=dim;
    for (int q=1; q<=Q; q++)
    {
        fin>>a>>b;
        dim=0;
        sol=0;
        for (d=1; d<=aux1; d++)
            if  (b%P[d]==0)
            {
                divi[++dim]=P[d];
                ok=1;
            }
        if (ok==0)
            divi[++dim]=b;
        for (j=1; j<=dim; j++)
        sub[j]=0;
        val=(1<<dim)-1;
        for (i=1; i<=val; i++)
        {
            pr=1;
            nr=0;
            aux2=dim;
            while (sub[aux2]==1)
            {
                sub[aux2]=0;
                aux2--;
            }
            sub[aux2]=1;
            for (j=1; j<=dim; j++)
                if (sub[j]==1)
                {
                    pr*=divi[j];
                    nr++;
                }
            if (nr%2==0)
                sol-=a/pr;
            else
                sol+=a/pr;
        }
        fout<<a-sol<<"\n";
    }
}