#include <fstream>

using namespace std;

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

long long np,p[30],a,b;
int main()
{
    int t;
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        np=0;
        if(b%2==0)
            p[++np]=2;
        while(b%2==0)
            b/=2;
        long long f=3;
        while(b!=1)
        {
            int ok=0;
            if(f*f>b) f=b;
            while(b%f==0)
            {
                ok=1;
                b/=f;
            }
            if(ok) p[++np]=f;
            f+=2;
        }
        long long lim=1;
        for(int i=1;i<=np;++i) lim<<=1;
        long long rez=0;
        for(int i=1;i<lim;++i)
        {
            int cop=i,nb=0,care=1;
            long long prod=1;
            while(cop)
            {
                if(cop&1)
                {
                    nb++;
                    prod*=p[care];
                }
                cop>>=1;
                care++;
            }
            if(nb%2==0) prod*=-1;
            rez+=a/prod;
        }
        fout<<a-rez<<'\n';
    }
    return 0;
}