#include <bits/stdc++.h>
#define INF 1000000
#define ll long long
using namespace std;

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

int Q;
ll A, B;
bool ciur[INF + 5];
vector<ll> prime, fact;

ll solve() {
    fact.clear();
    int i = 0;
    while (prime[i] * prime[i] <= B) {
        if (B % prime[i] == 0) {
             fact.push_back(prime[i]);
             while (B % prime[i] == 0)
                 B /= prime[i];
        }
        ++i;
    }
    if (B > 1) fact.push_back(B);

    int N = fact.size();
    ll ans = 0;
    for (int mask = 1; mask < (1 << N); ++mask) {
        ll P = 1;
        int nr = 0;
        for (int i = 0; i < N; ++i)
            if (mask & (1 << i)) P *= fact[i], ++nr;

        if (nr % 2) ans += A / P;
        else ans -= A / P;
    }

      return A - ans;
}
int main()
{
    for (int i = 2; i <= INF; ++i)
        if (!ciur[i]) {
            prime.push_back(1ll * i);
            for (int j = 2; j <= INF/ i; ++j)
                ciur[i * j] = 1;
        }

    f >> Q;
    while (Q--)
        f >> A >> B, g << solve() << '\n';

    return 0;
}