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

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

void usain_bolt()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

vector<int> sieve()
{
    int sq = int(1e6);
    vector<int> sol = {2};
    vector<bool> f(sq + 1, false);
    for (int i = 3; i < sq; i += 2) {
        if (f[i]) {
            continue;
        }
        sol.push_back(i);
        for (int j = i + i; j < sq; j += i) {
            f[j] = true;
        }
    }

    return sol;
}

void solve(vector<int>& primes)
{
    long long a, b;
    fin >> a >> b;
    long long sol = a;
    vector<long long> found;
    for (auto prime : primes) {
        if (b % prime) {
            continue;
        }
        if (prime * prime > b) {
            continue;
        }
        while (b % prime == 0) {
            b /= prime;
        }
        found.push_back(prime);
    }
    if (b > 1) {
        found.push_back(b);
    }
    int sz = (int)found.size();
    for (int i = 1; i < (1 << sz); ++i) {
        int cnt = 0;
        long long prod = 1;
        for (int j = 0; j < sz; ++j) {
            if (i & (1 << j)) {
                ++cnt;
                prod *= found[j];
            }
        }
        sol += (cnt % 2 == 0 ? 1 : -1) * (a / prod);
    }
    fout << sol << '\n';

    return;
}

int main()
{
    usain_bolt();
    
    int tt;
    
    vector<int> primes = sieve();

    fin >> tt;
    while (tt--) {
        solve(primes);
    }
    return 0;
}