#include <bits/stdc++.h>

using namespace std;

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

long long n,a,b,v[1000000],traian,ii,d,p,cc;
long long fprim[800000];
bool prim[1000000];

void prec()
{
    for (int i = 2; i < 1000000 ; i++)
        if (prim[i]==0)
        {
            for (int j = 2 * i; j < 1000000; j += i)
                prim[j] = 1;
            fprim[++fprim[0]] = i;
        }
}

int main()
{
    prec();
    in>>n;
    for(ii=1; ii<=n; ii++)
    {
        in>>a>>b;
        traian=0;
        d = 1;
        cc=0;
        while(b > 1)
        {
            p = 0;
            while(b % fprim[d] == 0)
            {
                ++p;
                b /= fprim[d];
            }
            if(p>0)
            {
                v[cc]=fprim[d];
                cc++;
            }
            ++ d;
            if (fprim[d] > sqrt(b) && b > 1)
            {
                v[cc++] = b;
                b=1;
            }
        }
        for(long long i=0; i < (1<<cc); i++)
        {
            long long p=1,traian2=0;
            for(long long  j=0; j < cc; j++)
            {
                if ((i & (1 << j)) > 0)
                {
                    p*=v[j];
                    traian2++;
                }
            }
            if(p==1)
                continue;
            if(traian2%2==0)
                traian-=floor(a/p);
            else
                traian+=floor(a/p);
        }
        out<<a-traian<<'\n';
    }
    return 0;
}