#include <fstream>
#include <cmath>

using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long ciur[1000005];
long long vecp[1000005],cntp=0;
long long vecf[1000005],cntf=0;
long long sum=0;
void ciurul()
{
    ciur[0]=1;
    ciur[1]=1;
    for(long long i=4; i<1000005; i+=2)
        ciur[i]=1;
    for(long long i=3; i*i<1000005; i+=2)
    {
        if(ciur[i]==0)
        {
            for(long long j=i*i; j<1000005; j+=2*i)
                ciur[j]=1;
        }
    }
    cntp=1;
    vecp[cntp]=2;
    for(long long i=3; i<1000005; i+=2)
        if(ciur[i]==0)
            vecp[++cntp]=i;
}
void fprimi(long long m)
{
    long long baza,poz=1;
    baza=vecp[poz++];
    if(m%baza==0)
    {
        while(m%baza==0)
            m/=baza;
        vecf[++cntf]=baza;
    }
    while(baza*baza<=m)
    {
        baza=vecp[poz++];
        if(m%baza==0)
        {
            while(m%baza==0)
                m/=baza;
            vecf[++cntf]=baza;
        }
    }
    if(m>1)
    {
        vecf[++cntf]=m;
    }
//    for(long long i=1; i<=cntf; i++)
//        cout<<vecf[i]<<" ";
//    cout<<'\n';
}
void backt(long long k,long long n,long long prod,long long nr)
{
    if(k==cntf+1)
    {
        if(nr!=1)
            sum+=pow(-1,nr)*(n/prod);
    }
    else
    {
        backt(k+1,n,prod,nr);
        nr++;
        prod*=vecf[k];
        backt(k+1,n,prod,nr);
        nr--;
        prod/=vecf[k];
    }
}
void solve (long long n,long long m)
{
    cntf=0;
    sum=0;
    fprimi(m);
    backt(1,n,1,1);
    cout<<n-sum<<'\n';
}
int main()
{
    ciurul();
    long long t;
    cin>>t;
    while(t>0)
    {
        long long a,b;
        cin>>a>>b;
        solve(a,b);
        t--;
    }
    return 0;
}