#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(b % it == 0)
            {
                divB.push_back(it);

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

    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 nr = 0;

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

            if(nr % 2 == 0)
                ans += a / prod;
            else
                ans -= 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;
}