///solutia consta in:
///a precalcula nr prime < ca 10^6 = sqrt ( 10^12 )
///il descompunem pe B in factori primi, mergand pe numerele prime
///aplicam principiul includerii si excluderii


#include <fstream>

using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long q,i,j,a,b;
long long p[100000];
long long m;
bool ciur[1000001];
void genereaza()
{
    for(i=2;i<=1000000;i++)
        if(ciur[i]==0)
        {
            p[++m]=i;
            for(j=i*i;j<=1000000;j++)
                ciur[j]=1;
        }
}
void pinex(long long a,long long b)
{
    long long i,nrdiv=0,divi[30],prod,sol=a,nr;
    for(i=1;p[i]*p[i]<=b&&i<=m;i++)
    {
        if(b%p[i]==0)
        {
            while(b%p[i]==0)
                b/=p[i];
            divi[++nrdiv]=p[i];
        }
    }
    if(b>1)
        divi[++nrdiv]=b;
    for(i=1;i<(1<<nrdiv);i++)
    {
        nr=0;
        prod=1;
        for(j=0;j<nrdiv;j++)
        {
            if((1<<j)&i)
            {
                nr++;
                prod*=1LL*divi[j+1];
            }
        }
        if(nr%2)
            nr=-1;
        else
            nr=1;
        sol+=1LL*nr*a/prod;
    }
    cout<<sol<<'\n';
}
int main()
{
    genereaza();
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>a>>b;
        pinex(a,b);
    }
    return 0;
}