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

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

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

ll calc() {
    fact.clear();
    int j = 0;
    while (prime[j] * prime[j] <= B) {
        if (B % prime[j] == 0) {
            fact.push_back(prime[j]);
            while (B % prime[j] == 0)
                B /= prime[j];
        }
        ++j;
    }
    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)) ++nr, P *= fact[i];

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

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

    fin >> Q;
    while (Q--) {
        fin >> A >> B;
        fout << calc() << '\n';
    }
    return 0;
}