#include <fstream>

using namespace std;
long long a,b,i,j,t,p,s,nr,afis,v[1000005],m,r;
bool e[1000005],u[1000005],OK;
const long long c=1000000;
int main()
{
    ifstream f("pinex.in");
    ofstream g("pinex.out");

    for(i=2;i*i<=c;i++)
    if(!e[i])
    for(j=i*i;j<=c;j=j+i)
    e[j]=1;
f>>m;
for(r=1;r<=m;r++)
{
    f>>a>>b;
    for(i=2;i*i<=b;i++)
    if(!e[i] && b%i==0)
    v[++t]=i;
    for(i=1;i<=t;i++)
    while(b%v[i]==0)
    b/=v[i];
    if(b!=1)
    v[++t]=b;

    while(!OK) ///aprindem si stingem becuri
    {
        OK=1; p=1; s=1; nr=0;
        while(p<=t)
        {
            if(OK)
            {
                if(u[p])
                u[p]=0;
                else
                {
                    u[p]=1;
                    OK=0;
                    s*=v[p];
                    nr++;
                }
            }
            else
            {
                if(u[p])
                {
                    s*=v[p];
                    nr++;
                }
            }
            p++;
        }
        if(nr%2)
        afis-=a/s;
        else
        afis+=a/s;
    }
g<<afis<<'\n';
t=0;OK=0;afis=0;
for(i=1;i<=c;i++)
u[i]=0;
}

    return 0;
}