#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

bool ciur[1000999];
int prime[1000999],nrprime,m,a,b,mask,c,i,j;

int main()
{
    ciur[2]=1;
    prime[1]=2;
    nrprime=1;
    for (i=2;2*i<1000005;i++)
    {
        if (!ciur[i])
        {
            for (j=2*i;j<1000005;j+=i)
            {
                ciur[j]=true;
            }
            prime[++nrprime]=i;
        }
    }
    fin>>m;
    for (i=1;i<=m;i++)
    {
        j=1;
        int factori[101],f=0,nrcur,coef=1,rezultat=0;
        fin>>a>>b;
        while (b>1)
        {
            if (b%prime[j]==0)
            {
                factori[++f]=prime[j];
                while (b%prime[j]==0)
                    b/=prime[j];
            }
            j++;
        }
        for (mask=0;mask<(1<<f);mask++)
        {
            c=mask;
            nrcur=1;
            coef=1;
            for (j=1;j<=f;j++)
            {
                if (c%2==1)
                    nrcur*=factori[j],coef=-coef;
                c/=2;
            }
            rezultat=rezultat+coef*(a/nrcur);
        }
        fout<<rezultat<<'\n';
    }
    return 0;
}