#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll BMAX = 1e12;
const ll SQRT_BMAX = 1e6;
vector<int> prime;
bool ciur[SQRT_BMAX+1];

void _ciur ()
{
    for (int i = 2; i <= SQRT_BMAX; i++)
    {
        if (!ciur[i]) prime.push_back(i);
        for (int k = 2*i; k <= SQRT_BMAX; k += i)
        {
            ciur[k] = 1;
        }
    }
}

int main ()
{
    freopen("pinex.in" , "r" , stdin);
    freopen("pinex.out" , "w" , stdout);
    int m; cin >> m;
    _ciur();
    while (m--)
    {
        ll a, b; cin >> a >> b;
        ll b_i = b;
        vector<int> fact;
        for (auto &p : prime)
        {
            if (p * p > b_i) break;
            if (b % p == 0) {
                fact.push_back(p);
                while (b % p == 0) b /= p;
            }
        }
        if ( b > 1) fact.push_back(b);
        ll ans = 0;

        for (int mask = 1; mask < (1 << fact.size()); mask++)
        {
            ll prod = 1;
            for (int bit = 0; (1 << bit) <= mask; bit++)
            {
                if ((1 << bit) & mask) prod *= fact[bit];
            }
        //    cout << prod << '\n';
            if (__builtin_popcount(mask) % 2 == 0)
            {
                ans -= a / prod;
            }
            else {
                ans += a / prod;
            }
        }
        cout << a - ans << '\n';
        fact.clear();
    }
}