#include <fstream>
#include <vector>

using namespace std;

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

const int SQRTVALMAX = 1e6;

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

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

    for(int i = 3; i * i <= SQRTVALMAX; i += 2)
        if(!d[i])
        {
            for(int j = i * i; j <= SQRTVALMAX; j += 2 * i)
                d[j] = 1;
        }

    for(int i = 3; i <= SQRTVALMAX; i += 2)
        if(!d[i])
            primes.push_back(i);
}

void Pinex(long long a, long long b)
{
    vector <int> divB;

    for(auto it : primes)
        if(1LL * it * it <= b)
        {
            if(b % it == 0)
            {
                divB.push_back(it);

                while(b % it == 0)
                    b /= it;
            }
        }
        else
            break;

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

    long long ans = 0;

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

        for(int bit = 0; bit < divB.size(); bit++)
            if(bk & (1 << bit))
                prod *= divB[bit], sign *= -1;

        ans += sign * (a / prod);
    }

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

int main()
{
    Ciur();

    int t;
    fin >> t;

    long long A, B;
    while(t--)
    {
        fin >> A >> B;
        Pinex(A, B);
    }

    return 0;
}