#include <iostream>

using namespace std;

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 * sd[j] < N; ++j)
            sd[i * prime[j]] = j;
    }
}

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

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();
    }
    return 0;
}