#include <fstream>
#include <vector>

using namespace std;

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

int M;
long long A, B;

bool isPrime[1000005];
vector <int> primes;

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

    for(int i = 3; i <= 1000000; i += 2)
        if(!isPrime[i])
        {
            if(i > 50000)
                i++, i--;

            primes.push_back(i);

            for(long long j = 1LL * i * i; j <= 1000000; j += 2 * i)
                isPrime[j] = 1;
        }
}

void Solve()
{
    fin >> A >> B;

    vector <int> divB;

    for(int i = 0; 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++)
    {
        int sign = 1;
        long long pDiv = 1;

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

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

    fout << ans << '\n';
}

int main()
{
    InitPrimes();

    fin >> M;

    while(M--)
        Solve();

    return 0;
}