#include <fstream>
#include <cstring>

using namespace std;

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


const int MAX_VALUE = 1000000;
const int DIM = 100005;

long long n;
long long primeCnt = 0, vCnt = 0, sol = 0;
long long prime[DIM], v[DIM / 1000 + 1];
bool f[MAX_VALUE + 5], g[DIM / 1000 + 1];

void eratostene() {
    for (int i = 2; i <= MAX_VALUE; i++) {
        if (!f[i]) {
            prime[++primeCnt] = i;
            for (int j = 2 * i; j <= MAX_VALUE; j += i)
                f[j] = true;
        }
    }
}

long long solve(long long a, long long b) {
    long long val = b;
    vCnt = 0;
    for (int j = 1; val != 1 && prime[j] <= b / prime[j]; j++) {
        if (val % prime[j] == 0) {
            v[++vCnt] = prime[j];
            while (val % prime[j] == 0)
                val /= prime[j];
        }
    }
    if (val != 1)
        v[++vCnt] = val;

    sol = a;
    memset(g, 0, sizeof(g));
    while (g[0] == 0) {
        long long j = vCnt;
        while (g[j] == 1) {
            g[j] = 0;
            j--;
        }
        g[j] = 1;

        if (j != 0) {
            long long cnt = 0;
            val = 1;
            for (int k = 1; k <= vCnt; k++) {
                cnt += g[k];
                if (g[k] == 1)
                    val *= v[k];
            }

            if (cnt % 2 == 0) sol += a / val;
            else                sol -= a / val;

        }
    }

    return sol;
}

int main() {
    eratostene();

    fin >> n;
    for (int i = 1; i <= n; i++) {
        long long a, b;
        fin >> a >> b;
        fout << solve(a, b) << '\n';
    }

    return 0;
}