#include<fstream>
#include<bitset>
#include<vector>
#define ll long long
std::ifstream fin("pinex.in");
std::ofstream fout("pinex.out");
std::bitset<1000001>f;
std::vector<ll>primes;
std::vector<ll>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);
}
bool isPrime(ll n)
{
    if(n<2 || (n>2 && n%2==0))
        return false;
    for(int i=0; i<primes.size() && primes[i]*primes[i]<=n; ++i)
        if(!(n%primes[i]))
            return false;
    return true;
}
void get_prime_div()
{
    divs.resize(0);
    for(auto &it:primes)
        if(!(b%it))
        {
            divs.push_back(it);
            if(b/it>1000000 && isPrime(b/it))
                divs.push_back(b/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<100>bits=i;
        int cnt=0;
        for(int j=0; j<100 && j<nr; ++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;
}