#include <iostream>
#include <fstream>
#include <cmath>
#define NUM 30
#define NUM_MAX 100000
typedef long long lint;
lint fact[NUM], a, b, n;
int fprim[NUM_MAX];
bool prim[NUM_MAX];
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
void precalc()
{
    for(int i = 2; i < NUM_MAX; ++i)
    {
        if(!prim[i])
        {
            for(int j = i * 2; j < NUM_MAX; ++j)
                prim[j] = true;
            fprim[++fprim[0]] = i;
        }
    }
}
void solve()
{
    lint num_f = 0, d = 0, sol;
    while (b > 1)
    {
        d++;
        if(!(b % fprim[d]))
        {
            fact[++num_f] = fprim[d];
            while(!(b % fprim[d]))
                b /= fprim[d];
        }
        if(fprim[d] > sqrt(b) && b > 1)
        {
            fact[++num_f] = b;
            b = 1;
        }
    }
    sol = a;
    for(int i = 1; i < (1 << num_f) ; ++i)
    {
        lint nr = 0, prod = 1;
        for(int j = 0; j < num_f; ++j)
            if((1 << j) & i)
            {
                prod = 1LL * prod * fact[j + 1];
                nr++;
            }
        if(nr & 1)
            nr = -1;
        else
            nr = 1;
        sol = sol + 1LL * a * nr / prod;
    }
    g << sol << "\n";
}
int main()
{
    precalc();
    f >> n;
    while(n--)
    {
        f >> a >> b;
        solve();
    }
    f.close();
    g.close();
}