/*
    Keep It Simple!
*/

#include <fstream>
#include <cmath>

#define Upper_Bound 1000000
#define ll long long

using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

const int Max_PrimeC = 90000;

ll T,A,B;
int p_count,primes[Max_PrimeC],factors[Max_PrimeC],f_count;
bool seen[Upper_Bound];

void GeneratePrimes()
{
    primes[++p_count] = 2;
    for(int i=3; i <= Upper_Bound; i+=2)
    {
        if(!seen[i])
        {
            primes[++p_count] = i;
            for(int j=i; j<= Upper_Bound; j+=i)
                seen[j] = 1;
        }
    }
}

void ComputeFactors(ll B)
{
    int idx = 1;
    while(B!=1)
    {
        if(!(B%primes[idx])) factors[++f_count] = primes[idx];
        while(!(B%primes[idx])) B/=primes[idx];
        idx++;

        if(factors[idx] > sqrt(B) && B > 1)
        {
            factors[++f_count] = B;
            B = 1;
        }
    }
}

ll pinex(ll A,ll B)
{

    GeneratePrimes();

    f_count = 0;
    ComputeFactors(B);

    ll solution = A;

    for(int i=1; i < (1 << f_count); ++i)
    {
        int sign = 0;
        ll prod = 1;
        for(int j=0; j < f_count; j++)
            if( (1<<j) & i)
            {
                prod = 1LL * factors[j+1] * prod;
                sign ++;
            }

        if(sign%2) sign = -1;
        else sign = 1;

        solution = solution + 1LL * sign * A / prod;
    }
    return solution;
}

void Solve()
{
    cin >> T;

    while(T--)
    {
        cin >> A >> B;
        cout << pinex(A,B) << '\n';
    }
}

int main()
{
    Solve();
    return 0;
}