#include <bits/stdc++.h>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long d,t,i,T,pas,n,a,nr,produs,j,sol,b,v[1010],prim[1000010];
bool ciur[1000011];

int main()
{
    for(d=2;d<=1000001;d++)
        if(ciur[d]==0)
        {
            t++,prim[t]=d;
            for(i=d*d;i<=1000001;i=i+d)ciur[i]=1;
        }


    f>>T;
    for(pas=1;pas<=T;pas++)
    {
        f>>a>>b;
        n=0;
        t=1;
        sol=0;
        while(prim[t]*prim[t]<=b)
        {
            if(b%prim[t]==0)
            {
                n++,v[n]=prim[t];
                while(b%prim[t]==0)b/=prim[t];
            }
            t++;
        }
        if(b!=1)n++,v[n]=b;

        for(i=1;i<(1<<n);i++)
        {
            nr=0;
            produs=1;

            for(j=0;j<n;j++)
            {
                if((i&(1<<j))!=0)
                {
                    nr++;
                    produs=produs*v[j+1];
                }
            }

            if(nr%2==1)sol+=a/produs;
            else sol-=a/produs;
        }
        g<<a-sol<<'\n';
    }
    return 0;
}