#include <fstream>
#include <vector>

using namespace std;

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

const int N = 1e6 + 7;

vector < int > prime, div;
int sd[N], ans, a;

void precalc() {

    for (int i = 2; i < N; ++i) {
        if (!sd[i])
            sd[i] = prime.size(),
            prime.push_back(i);
        for (int j = 0; j <= sd[i] && 1LL * i * prime[j] < N; ++j)
            sd[i * prime[j]] = j;
    }
}

void bkt(int i = 0, int coef = 1, long long prod = 1) {
    if (i == div.size()) {
        ans += coef * (a / prod);
        return;
    }
    bkt(i + 1, coef, prod);
    if (a / prod < div[i])
        return;
    if (a / div[i] < prod)
        return;
    if (div[i] * prod < 0)
        return;
    bkt(i + 1, -coef, prod * div[i]);
}

int main()
{
    int b, t;
    precalc();
    cin >> t;
    while (t--) {
        cin >> a >> b;
        div.clear();
        ans = 0;
        for (int i = 0; i < prime.size(); ++i) {
            if (!(b % prime[i])) {
                div.push_back(prime[i]);
                while (!(b % prime[i]))
                    b /= prime[i];
            }
        }
        if (b - 1)
            div.push_back(b);
        bkt();
        cout << ans << '\n';
    }
    return 0;
}