#include <fstream>
#include <vector>

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

const int VM = 1e6 + 7;

std::vector < int > prime;

long long divzr[20];

bool prm[VM];

void precalc_p() {
    prime.push_back(2);
    for (int i = 4; i < VM; i += 2)
        prm[i] = 1;
    for (int i = 3; i < VM; i += 2)
        if (!prm[i]) {
            prime.push_back(i);
            if (i < VM / i)
                for (int j = i * i; j < VM; j += 2 * i * i)
                    prm[j] = 0;
        }
}


long long ans(0), a, siz(0);

void peenex(int poz, long long num, int k) {
    if (poz == siz) {
        ans += a / num * k;
        return;
    }
    peenex(poz + 1, num, k);
    if (num <= a / divzr[poz])
        peenex(poz + 1, num * divzr[poz], - k);
}

int main()
{
    int t;
    long long b;
    cin >> t;
    precalc_p();
    while (t--) {
        cin >> a >> b;
        siz = 0;
        ans = 0;
        for (int i = 0; i < prime.size() && b > 1 && prime[i] * prime[i] <= b; ++i)
            if (b % prime[i] == 0) {
                divzr[siz++] = (prime[i]);
                while (b % prime[i] == 0)
                    b /= prime[i];
            }
        if (b != 1)
            divzr[siz++] = (b);
        peenex(0, 1, 1);
        cout << ans << '\n';
    }
    return 0;
}