#include <fstream>
#include <vector>

using namespace std;

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

const int CIURMAX = 1000000;

bool d[CIURMAX + 5];
vector <int> primes;

void InitPrimes()
{
    primes.push_back(2);

    for(int i = 3; i * i <= CIURMAX; i += 2)
        if(!d[i])
        {
            primes.push_back(i);

            for(int j = i * i; j <= CIURMAX; j += 2 * i)
                d[j] = 1;
        }
}

long long Solve(long long A, long long B)
{
    vector <long long> divB;

    for(int i = 0; i < primes.size() && 1LL * primes[i] * primes[i] <= B; i++)
        if(B % primes[i] == 0)
        {
            divB.push_back(primes[i]);

            while(B % primes[i] == 0)
                B /= primes[i];
        }

    if(B != 1)
        divB.push_back(B);

    long long ans = 0;

    for(int bk = 0; bk < (1 << (divB.size())); bk++)
    {
        long long pDiv = 1;
        int sign = 1;

        for(int j = 0; j < divB.size(); j++)
            if((bk & (1 << j)) != 0)
            {
                pDiv *= divB[j];
                sign *= -1;
            }

        ans += sign * (A / pDiv);
    }

    return ans;
}

int main()
{
    InitPrimes();

    int T;
    long long A, B;

    fin >> T;

    while(T--)
    {
        fin >> A >> B;
        fout << Solve(A, B) << '\n';
    }

    return 0;
}