#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

long long n,x;
int i;

bitset<1000005> ciur;
vector<int> primes;


void prec(int x)
{
    ciur[0]=ciur[1]=1;
    primes.push_back(2);
    for(i=3;i*i<=x;i+=2)
        if(!ciur[i])
            for(int j=i*i;j<=x;j+=i)
                ciur[j]=1;
    for(i=3;i<=x;i+=2)
        if(!ciur[i])
            primes.push_back(i);
}

void solve()
{
    fin>>n>>x;
    if(x==1)
    {
        fout<<n<<'\n';
        return;
    }
    vector<long long> p;
    for(i=0;1LL*primes[i]*primes[i]<=x;i++)
    {
        if(x%primes[i]==0)
        {
            p.push_back(primes[i]);
            while(x%primes[i]==0)
                x/=primes[i];
        }
    }
    if(x>1)
        p.push_back(x);
    int lim=1<<p.size();
    long long ans=n;
    for(i=1;i<lim;i++)
    {
        int semn=1;
        long long pr=1;
        if(__builtin_popcount(i)&1)semn=-1;
        for(int j=0;j<p.size();j++)
            if(i&(1<<j))
                pr*=p[j];
        ans+=semn*(n/pr);
    }
    fout<<ans<<'\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    fin>>t;
    prec(1e6);
    while(t--)
        solve();
    return 0;
}