#include<fstream>
#include<vector>
#define ll unsigned long long
#pragma GCC optimize("unroll-loops", "O3")
std::ifstream fin("pinex.in");
std::ofstream fout("pinex.out");
std::vector<ll>divs;
ll a, b;
inline void decomp(ll n)
{
    ll p, d;
    for(p=0; n%2==0; ++p, n/=2);
    if(p)
        divs.push_back(2);
    for(d=3; d*d<=n; d+=2)
    {
        for(p=0; n%d==0; ++p, n/=d);
        if(p)
            divs.push_back(d);
    }
    if(n>1)
        divs.push_back(n);
}
inline ll solve()
{
    divs.resize(0);
    decomp(b);
    int nr=divs.size();
    ll ans=0;
    for(ll i=1; i<(1<<nr); ++i)
    {
        ll local=1;
        int cnt=0;
        for(int j=0; j<nr; ++j)
            if((1<<j)&i)
            {
                local*=divs[j];
                ++cnt;
            }

        local=a/local;
        if(cnt%2)
            ans+=local;
        else
            ans-=local;
    }
    return a-ans;
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    int t;
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        fout<<solve()<<'\n';
    }
    return 0;
}