#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()
{
    for(int i = 2; i * i <= ValMAX; ++i)
        if(c[i] == 0)
        {
            for(int j = i + i; j <= ValMAX; j += i)
                c[j] = 1;
        }
    for(int i = 2; i <= ValMAX; ++i)
        if(!c[i])
            prim.push_back(i);
}
void solve(ll a, ll b)
{

    vector <int> div;
    int d = 0;
    ll ans = 0;
    while(1LL * prim[d] * prim[d] <= b)
    {
        if(b % prim[d] == 0)
        {
            div.push_back(prim[d]);
            while(b % prim[d] == 0)
                b /= prim[d];
        }
        d++;
    }
    if(b != 1)
        div.push_back(b);

    for(ll conf = 0; conf < (1LL << div.size()); ++ conf)
    {
        int sgn = 1;
        ll produs = 1;
        for(int i = 0; i < div.size(); ++i)
            if((1LL << i) & conf)
            {
                produs *= div[i];
                sgn *= -1;
            }
        ans += (a/ produs) * sgn;
    }
    g << ans << '\n';
}
int main()
{
    ciur();
    f >> T;
    while(T--)
    {
        f >> a >> b;
        solve(a,b);
    }
    f.close();
    g.close();
    return 0;
}