#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

typedef long long LL;
const int MAXN = 1000000;

LL A, B;
LL Ans;
bool Prim[MAXN + 10];
LL Fact[40];
vector <LL> Prime;

void Ciur ()
{
    int i, j;

    Prime.push_back (2);
    for (i = 3; i <= MAXN; i += 2){
        if (!Prim[i])
            Prime.push_back (i);

            for (j = i + i; j <= MAXN; j += i)
                Prim[j] = 1;
    }

}

LL Solve ()
{
    int i = 0, j, N, lev;
    LL prod;
    N = Prime.size ();

    while (B > 1 && i < N && (long long) Prime[i] * Prime[i] < B){
        if (B % Prime[i] == 0){
            Fact[++ Fact[0]] = Prime[i];

            while (B % Prime[i] == 0)
                B /= Prime[i];
        }
        i ++;
    }

    if (B > 1)
        Fact[++ Fact[0]] = B;

    for (i = 1; i < (1LL << Fact[0]); i ++){
        lev = 0;
        prod = 1;

        for (j = 0; j < Fact[0]; j ++)
            if (i & (1 << j))
                prod *= (long long) Fact[j + 1], lev ++;

        if (lev & 1)
            Ans += (A / prod);
        else
            Ans -= (A / prod);
    }

    return A - Ans;
}

int main()
{
    int T;

    Ciur ();
    for (in >> T; T; T --){
        in >> A >> B;
        Ans = 0;
        Fact[0] = 0;
        out << Solve () << "\n";
    }

    return 0;
}