#include <fstream>
#include <vector>
#define ll long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
vector <int> prim;
const int ValMAX = 1e6;
int c[ValMAX + 10];
ll T, a, b;
void ciur()
{
    c[1] = c[0] = 1;
    for(int i = 2; i * i <= ValMAX; ++i)
        if(c[i] == 0)
        {
            for(int j = 2 * i; j <= ValMAX; j += i)
                c[j] = 1;
        }
    for(int i = 2; i <= ValMAX; ++i)
        if(c[i] == 0) prim.push_back(i);
}
void solve(ll a, ll b)
{
    ll ans = 0 ;
    vector <int> div;
    int d = 0;
    while(1LL * prim[d] * prim[d] <= b)
    {
        if(b % prim[d] == 0)
        {
            while(b % prim[d] == 0)
                b /= prim[d];
            div.push_back(prim[d]);
        }
        d++;
    }
    if(b != 1)
        div.push_back(b);

    for(int divb = 0; divb < (1 << (div.size()) ); ++ divb)
    {
        ll prod = 1, sgn = 1;

        for(int k = 0 ; k < div.size(); ++k)
            if(divb & (1 << k))
                prod *= div[k], sgn *= -1;

        ans += sgn * (a/prod) ;
    }
    g << ans << '\n';
}
int main()
{
    ciur();
    f >> T;
    while(T--)
    {
        f >> a >> b;
        solve(a,b);
    }
    f.close();
    g.close();
    return 0;
}