#include <fstream>
#include <cmath>
#include <bitset>

using namespace std;

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

long long m,A,B;
long long factori[40], prime[80000];
bitset <1000000> bs;

void ciur()
{
    int p = 0;
    for(int i = 2; i < 1000000; i++)
        if(!bs[i])
        {
            prime[++p] = i;
            for(int j = i + i; j < 1000000; j += i) bs[j] = 1;
        }
}

void solve()
{
    long long p = 0, k = 0;
    while(B > 1)
    {
        k++;
        if(!(B % prime[k]))
        {
            factori[++p] = prime[k];
            while(!(B % prime[k])) B /= prime[k];
        }
        if(prime[k] > sqrt(B) && B > 1)
        {
            factori[++p] = B;
            B = 1;
        }
    }
    
    long long sol = A;
    for(int i = 1; i < (1 << p); i++)
    {
        long long produs = 1, plusminus = 0;
        for(int j = 1; j <= p; j++)
            if(i & (1 << (j - 1)))
            {
                produs = 1LL * produs * factori[j];
                plusminus++;
            }
        if(plusminus % 2) plusminus = -1;
        else plusminus = 1;
        
        sol = sol + 1LL * A * plusminus / produs;
    }
    
    fout << sol << '\n';
}

int main()
{
    ciur();
    
    fin >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> A >> B;
        solve();
    }
}