#include <fstream>

using namespace std;

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

long long m,w[1000001],prim[100001],v[10001],nr,s,prod,fact[10001];
long long i,j,k,a,b,n;

int main()
{
    fin >> m;
    w[0] = w[1] = 1;
    for (i=2; i<=1000000; i++)
        if (w[i] == 0)
        {
            prim[++k] = i;
            for (j=i+i; j<=1000000; j+=i)
                w[j] = 1;
        }
    for (;m--;)
    {
        fin >> a >> b;
        s = n = 0;
        for (i=1; prim[i]*prim[i]<=b; i++)
            if (b%prim[i] == 0)
            {
                fact[++n] = prim[i];
                while (b%prim[i] == 0)
                    b /= prim[i];
            }
        if (b != 1)
            fact[++n] = b;
        for (i=0; i<=n; i++)
            v[i] = 0;
        while (v[0] == 0)
        {
            i = n;
            while (v[i] == 1 && i >= 1)
            {
                v[i] = 0;
                i--;
            }
            v[i] = 1;
            prod = 1;
            nr = 0;
            for (j=1; j<=n; j++)
                if (v[j] == 1)
                {
                    prod *= fact[j];
                    nr++;
                }
            if (nr%2 == 1)
                s -= a/prod;
            else
                s += a/prod;
        }
        fout << s << "\n";
    }
    return 0;
}