#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int PRIM=1000009;
bitset<1000009>viz;
int used[100005];
int p[PRIM/3],divi[100005];
void ciur()
{
    int i,j;
    p[++p[0]]=2;
    for(i=3;i*i<1000009;i+=2)
    {
        if(viz[i]==0)
        {
            for(j=i*i;j<1000009;j+=i)
            {
                viz[j]=1;
            }
        }
    }
    for(i=3;i<1000009;i+=2)
    {
        if(viz[i]==0) p[++p[0]]=i;
    }
}
void backtr(int k,int N,int A,int &step,int &rez)
{
    if(k==N+1)
    {
        rez+=A/step;
    }
    else
    {
        for(int i=used[k-1]+1;i<=divi[0];i++)
        {
            if(step*divi[i]<=A )
            {
                step*=divi[i];
                used[k]=i;
                backtr(k+1,N,A,step,rez);
                step/=divi[i];
            }
        }
    }
}
int main()
{
    ciur();
    int M,a,b,i,k,step,rez,tot=0;
    fin>>M;
    while(M--)
    {
        fin>>a>>b;
        k=0;tot=0;
        for(i=1;p[i]*p[i]<=b;i++)
        {
            if(b%p[i]==0)
            {
                divi[++k]=p[i];
                while(b%p[i]==0) b/=p[i];
            }
        }
        if(b>1) divi[++k]=b;
        divi[0]=k;
        for(i=1;i<=k;i++)
        {
            rez=0;step=1;
            backtr(1,i,a,step,rez);
            if(i%2==1) tot+=rez;
            else tot-=rez;
        }
        fout<<a-tot<<"\n";
    }
}