#include <fstream>
#include <vector>

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

const int VM = 1e6 + 7;

std::vector < int > prime;

std::vector < long long > pivotLaMatnanCurInfoarenaSifilelevoastreincluse;

int pos[VM];

void precalc_p() {
    prime.push_back(1);
    for (int i = 2; i < VM; ++i) {
        if (pos[i] == 0)
            prime.push_back(i);
        else
            for (int j = 1; j <= pos[i] && i <= VM / prime[j]; ++i)
                pos[i * prime[j]] = j;
    }
}

long long ans(0), a;

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

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