#include <iostream>
#include <fstream>
#include <cmath>
#define NUM 30
typedef long long lint;
lint fact[NUM], a, b, n;
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
void solve()
{
    lint num_f = 0, d = 2, sol;
    while (b > 1)
    {
        if (b % d == 0)
        {
            fact[++num_f] = d;
            while (b % d == 0)
                b /= d;
        }

        if (d > sqrt(b) && b > 1)
        {
            fact[++num_f] = b;
            b = 1;
        }

        if (d == 2) d++;
        else d += 2;
    }
    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()
{
    f >> n;
    while(n--)
    {
        f >> a >> b;
        solve();
    }
    f.close();
    g.close();
}