#include <bits/stdc++.h>

using namespace std;

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

double f[1001];

void factori(int n, int &idx) {
    for (int i = 2; i <= n; i++) {
        if (n % i == 0)
            f[idx++] = i;
        while (n % i == 0)
            n /= i;
    }
}

int main(void) {
    int m;
    double a, b;

    in >> m;
    while (m--) {
        int sum = 0, idx = 0;
        in >> a >> b;

        factori(a, idx);
        for (int i = 0; i < idx; i++)
                sum += floor(a / f[i]);

        for (int i = 0; i < idx - 1; i++)
            for (int j = i + 1; j < idx; j++)
                sum -= floor(a / f[i] * f[j]);

        long long produs = 1;
        for (int i = 0; i < idx; i++)
            produs *= f[i];
        
        sum += floor(a / produs);

        out << sum << '\n';
    }

    return 0;
}