#include <bits/stdc++.h>

using namespace std;

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

#define ll long long
#define MAX_P 1000000

ll M, A, B, fact[32];
int fprim[80000];
bool prim[MAX_P];

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

void solve()
{
    ll t = 0, d = 0;
    while (B > 1)
    {
		d++;
        if (B % fprim[d] == 0)
        {
            fact[++t] = fprim[d];
            while (B % fprim[d] == 0) B /= fprim[d];
        }

        if (fprim[d] > sqrt(B) && B > 1)
        {
            fact[++t] = B;
            B = 1;
        }
    }

    ll sol = A;
    for (int i = 1; i < (1 << t); i++)
    {
        ll nr = 0, prod = 1;
        for (int j = 0; j < t; j++)
        if ((1 << j) & i)
        {
            prod = 1LL * prod * fact[j + 1];
            nr++;
        }

        if (nr % 2) nr = -1;
        else nr = 1;

        sol = sol + 1LL * nr * A / prod;
    }

    g << sol << '\n';
}

int main()
{
	prec();
	f >> M;
   	for (int i = 1; i <= M; i++)
    {
        f >> A >> B;
   	    solve();
    }
    f.close();
    g.close();
    return 0;
}