#include <fstream>
#include <vector>
using namespace std;
typedef long long ll;

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

vector<int> primes;

void sieve(int lim)
{
    vector<bool> comp(lim + 1, false);
    for (int i = 2; i <= lim; i++)
        if (!comp[i])
        {
            primes.push_back(i);
            for (ll j = (ll)i * i; j <= lim; j += i)
                comp[j] = true;
        }
}

int main()
{
    sieve(1000000);

    int m;
    fin >> m;
    while (m--)
    {
        ll a, b;
        fin >> a >> b;

        // divizorii primi distincți ai lui b
        vector<ll> d;
        for (int p : primes)
        {
            if ((ll)p * p > b) break;
            if (b % p == 0)
            {
                d.push_back(p);
                while (b % p == 0) b /= p;
            }
        }
        if (b > 1) d.push_back(b);   // factor prim rămas

        int k = d.size();
        ll neprime = 0;
        for (int mask = 1; mask < (1 << k); mask++)
        {
            ll prod = 1;
            int bits = 0;
            for (int i = 0; i < k; i++)
                if (mask & (1 << i))
                {
                    prod *= d[i];
                    bits++;
                }
            if (bits & 1) neprime += a / prod;
            else          neprime -= a / prod;
        }

        fout << a - neprime << "\n";
    }
    return 0;
}