#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int main()
{
    long long q,a,b,i,j,k,rez,aux,cnt,nr;
    f>>q;
    while(q)
    {
        f>>a>>b;
        cnt=0; rez=a; k=1;
        int prim[1003]={0};
        for(i=2;i*i<=b;i++)
        {
            if(b%i==0)
            {
                cnt++;
                k=k*2;
                prim[cnt]=i;
                while(b%i==0)
                {
                    b=b/i;
                }
            }
        }
        if(b>1)
        {
            cnt++; k=k*2;
            prim[cnt]=b;
        }
        for(i=1;i<k;i++)
        {
            aux=1; nr=0; cnt=1;
            for(j=1;j<=k/2;j=j*2)
            {
                if((i&j)!=0)
                {
                    nr++;
                    aux=aux*prim[cnt];
                }
                cnt++;
            }
            if(nr%2==0)
            {
                rez=rez+a/aux;
            }
            else
            {
                rez=rez-a/aux;
            }
        }
        g<<rez<<'\n';
        q--;
    }
    return 0;
}