#include<fstream>
#include<bitset>
#include<vector>
#pragma GCC optimize("unroll-loops")
#define ll long long
std::ifstream fin("pinex.in");
std::ofstream fout("pinex.out");
std::bitset<1000005>f;
std::vector<int>primes;
std::vector<int>divs;
ll a, b;
void precalc()
{
    f[0]=f[1]=true;
    for(int i=2; i<=1000; ++i)
        if(!f[i])
            for(int j=i*i; j<=1000000; j+=i)
                f[j]=true;
    for(int i=2; i<=1000000; ++i)
        if(!f[i])
            primes.push_back(i);
}
void get_prime_div()
{
    divs.resize(0);
    for(auto &it:primes)
        if(!(b%it))
            divs.push_back(it);
}
ll solve()
{
    get_prime_div();
    int nr=divs.size();
    ll ans=0;
    for(ll i=1; i<(1<<nr); ++i)
    {
        ll local=1;
        std::bitset<40>bits=i;
        int cnt=0;
        for(int j=0; j<40; ++j)
            if(bits[j])
            {
                local*=divs[j];
                ++cnt;
            }

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