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

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

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

ll calc(ll A, ll B) {
    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 msk = 0; msk < (1 << N); ++msk) {
        ll P = 1;
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            if ((1 << i) & msk) ++cnt, P *= fact[i];

        if (cnt % 2) ans += A / P;
        else if (cnt > 0) ans -= A / P;
    }

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

    fin >> Q;
    while (Q--) {
        ll x, y;
        fin >> x >> y;
        fout << calc(x, y) << '\n';
    }

    return 0;
}