#include <fstream>
#include <vector>
#define ll long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
vector <int> prim;
int c[1000010];
ll T, a, b;
void ciur()
{
    c[1] = c[0] = 1;
    for(int i = 2; i <=1000000; ++i)
        if(c[i] == 0)
        {
            for(int j = 2 * i; j <= 1000000; j += i)
                c[i] = 1;
           // g << i << '\n';
            prim.push_back(i);
        }
}
void solve(ll a, ll b)
{
    ll ans = 0  ;
    vector <int> div;
    ll 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 < (1LL << div.size()); ++ divb)
    {
        ll prod = 1, sgn = 1;
        for(int val = 0 ; val < div.size(); ++val)
            if(divb & (1 << val))
                prod *= div[val], sgn *= -1;
        ans += (a/prod) * sgn;
    }
    g << ans << '\n';
}
int main()
{
    ciur();
    f >> T;
    while(T)
    {
        f >> a >> b;
        solve(a,b);
        T--;
    }
    f.close();
    g.close();
    return 0;
}