#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int nMax=11e5+5,MOD=1e9+7;

ll t,n,m,k,x,y,z,a,b,c,d,cnt,ans,rez,sum,poz;
ll v[nMax],primes[nMax],pr[20];
bool ok;
char ch;
string s;
map<int,int>mp;
bitset<nMax>f;
void pinex(ll val, ll cnt)
{
    rez=0;
    x=(1<<cnt);
    for(ll i=1; i<x; ++i)
    {
        z=1;
        for(ll bit=0; bit<cnt; ++bit)
            if(i&(1<<bit))
                z*=pr[bit+1];
        if(__builtin_popcount(i)%2)
            rez+=(val/z);
        else
            rez-=(val/z);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    for(int i=4; i<nMax; i+=2)
        f[i]=1;
    for(int i=3; i*i<nMax; ++i)
        if(!f[i])
            for(int j=i*i; j<nMax; j+=i*2)
                f[j]=1;
    for(int i=2; i<nMax; ++i)
        if(!f[i])
            primes[++cnt]=i;
    fin>>t;
    while(t--)
    {
        fin>>x>>y;
        cnt=0;
        ans=x;
        for(int d=1; primes[d]*primes[d]<=y; ++d)
            if(y%primes[d]==0)
            {
                pr[++cnt]=primes[d];
                while(y%primes[d]==0)
                    y/=primes[d];
            }
        if(y-1)
            pr[++cnt]=y;
        pinex(x,cnt);
        fout<<ans-rez<<'\n';
    }
}