#include <bits/stdc++.h>
#define NMAX 1000002

using namespace std;

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

bitset <NMAX> ciur;
vector <int> primes;

void solve(long long a, long long b)
{
    vector <int> div;
    for (int p : primes)
    {
        if (1LL * p * p > b) {
            break;
        } else if (b % p == 0) {
            div.push_back(p);
            while (b % p == 0)
                b /= p;
        }
    }

    if (b != 1)
        div.push_back(b);

    int n = div.size();
    long long ans = 0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        long long prod = 1;
        int bits_cnt = 0;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i)) {
                ++bits_cnt;
                prod = prod * div[i];
            }
        if (bits_cnt & 1)
            ans += a / prod;
        else
            ans -= a / prod;
    }
    fout << a - ans << '\n';
}

void precalculus()
{
    ciur[0] = ciur[1] = 1;
    for (int i = 2; i * i < NMAX; ++i)
        if (ciur[i] == 0)
            for (int j = i * i; j < NMAX; j += i)
                ciur[j] = 1;

    for (int i = 2; i < NMAX; ++i)
        if (ciur[i] == 0)
            primes.push_back(i);
    
}

int main()
{
    precalculus();
    int q;
    fin >> q;
    long long a, b;
    for (int i = 1; i <= q; ++i) {
        fin >> a >> b;
        solve(a, b);
    }
    return 0;
}