#include <bits/stdc++.h>
#define ll long long
#define N 1e6
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
ll t, A, B;
bitset <1000005> b;
vector <ll> prime;
vector <ll> factori;
void Ciur()
{
    ll i, j;
    b[0] = b[1] = 1;
    for (i = 4; i <= N; i += 2)
        b[i] = 1;
    for (i = 3; i * i <= N; i += 2)
        if (b[i] == 0)
            for (j = i * i; j <= N; j += 2 * i)
                b[j] = 1;

    prime.push_back(2);
    for (i = 3; i <= N; i += 2)
        if (b[i] == 0)
            prime.push_back(i);

}
vector <ll> GetFactors(ll x)
{
    ll d = 0, f, cnt; 
    vector <ll> sol;
    f = prime[d];
    while (x > 1)
    {
        cnt = 0;
        while (x % f == 0)
        {
            x /= f;
            cnt++;
        }
        if (cnt)
            sol.push_back(f);
        d++;
        if (d == prime.size())
        {
            sol.push_back(x);
            return sol;
        }
        else
        {
            f = prime[d];
            if (f * f > x)
                f = x;
        }
    }
    return sol;
}
void Test_Case()
{
    ll mask, n, i, cnt, p, sol = 0;
    factori = GetFactors(B);
    n = (1ll << factori.size()) - 1;
    for (mask = 1; mask <= n; mask++)
    {
        cnt = 0;
        p = 1;
        for (i = 0; i < factori.size(); i++)
            if (mask & (1ll << i))
            {
                cnt++;
                p *= factori[i];
            }
        if (cnt % 2 == 1)
            sol += A / p;
        else
            sol -= A / p;
    }
    fout << A - sol << "\n";
}
int main()
{
    fin >> t;
    Ciur();
    while (t--)
    {
        fin >> A >> B;
        Test_Case();
    }

    return 0;
}