#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#include <bits/stdc++.h>
#define endl '\n'
#endif

#define int int64_t

const int MAXVAL = 1e6+5;

bool ciur[MAXVAL];
vector<int> primes;
int fact[2000];

void precalc() {
    for (int i = 2; i < MAXVAL; i++) {
        if (!ciur[i]) {
            for (int j = 2 * i; j < MAXVAL; j += i) {
                ciur[j] = 1;
            }
            primes.push_back(i);
        }
    }
}

int get_fact(int n) {
    int cnt = 0, e = -1;
    while (n != 1) {
        e++;
        if (n % primes[e] == 0) {
            fact[++cnt] = primes[e];
            while (n % primes[e] == 0) {
                n /= primes[e];
            }
        }
        if (primes[e] * primes[e] > n && n != 1) {
            fact[++cnt] = n;
            n = 1;
        }
    }
    return cnt;
}

int solve(int a, int b) {
    int fcnt = get_fact(b);
    int ans = 0;
    for (int i = 1; i <= (1 << fcnt); i++) {
        int cnt = 0, p = 1;
        for (int j = 0; j < fcnt; j++) {
            if (i & (1 << j)) {
                p *= fact[j + 1];
                cnt++;
            }
        }
        if (cnt % 2 == 0) ans += a / p;
        else ans -= a / p;
    }
    return ans;
}

int32_t main() {
    int n, a, b;
    fin >> n;
    precalc();
    while (n--) {
        fin >> a >> b;
        fout << solve(a, b) << endl;
    }
    return 0;
}