#include <bits/stdc++.h>
using namespace std;

int t, k;
long long a, b;
long long d[2000001];

void calcDiv(long long b) {
    if (b % 2 == 0 && 2 <= a) {
        d[++k] = 2;
    }
    while (b % 2 == 0) {
        b /= 2;
    }
    for (long long i = 3; i * i <= b; i += 2) {
        if (i > a) {
            return;
        }
        if (b % i == 0 && i <= a) {
            d[++k] = i;
        }
        while (b % i == 0) {
            b /= i;
        }
    }
    if (b != 1 && b <= a) {
        d[++k] = b;
    }
}

long long calcLcm(long long a, long long b) {
    return a * b / __gcd(a, b);
}

int main() {
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    cin >> t;
    while (t--) {
        cin >> a >> b;
        k = 0;
        calcDiv(b);
        long long ans = 0;
        for (int i = 1; i <= (1 << k) - 1; ++i) {
            int pos = 1, lcm = 1, grade = 0;
            for (int j = i; j != 0; j >>= 1) {
                if (j & 1 == 1) {
                    lcm = calcLcm(lcm, d[pos]);
                    ++grade;
                }
                ++pos;
            }
            if (grade == 1 || (grade - 1) % 2 == 0) {
                ans += (a / lcm);
            } else {
                ans -= (a / lcm);
            }
        }
        ans = a - ans;
        cout << ans << "\n";
    }
}