#include <fstream>

using namespace std;
int f[1000010];
int P[200010];
int v[20];
int t, a, b, d, k, sol, i, j, p, e, biti, produs
;
int main () {
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    for (i=2;i<=1000000;i++)
        if (f[i] == 0) {
            P[++p] = i;
            for (long long j=i*1LL*i;j<=1000000;j+=i)
                f[j] = 1;
        }

    for (fin>>t;t--;) {
        fin>>a>>b;

        d = 1;
        k = 0;
        while (P[d] <= b/P[d] && b!=1 && d<=p) {
            e = 0;
            while (b%P[d] == 0) {
                e++;
                b/=P[d];
            }
            if (e!=0) {
                k++;
                v[k] = P[d];
            }
            d++;
        }
        if (b!=1) {
            v[++k] = b;
        }

        sol = 0;

        for (i=0;i<=k;i++)
            f[i] = 0;

        while (f[0]!=1) {
            j = k;
            while (f[j] == 1) {
                f[j] = 0;
                j--;
            }
            f[j] = 1;

            biti = 0;
            produs = 1;
            for (i=1;i<=k;i++)
                if (f[i] == 1) {
                    biti++;
                    produs *= v[i];
                }
            if (biti)
                if (biti%2 == 0)
                    sol -= a/produs;
                else
                    sol += a/produs;
        }
        fout<<a-sol<<"\n";

    }
    return 0;
}