#include<stdio.h>
using namespace std;
long long n1,nr,nr1,nr2,maxi,i,j,i10,t10,p,s,aux,n[502],m[502],a[1000002];
int pr[78499],d[102];
int main()
{
freopen("pinex.in","r",stdin);
freopen("pinex.out","w",stdout);
scanf("%lld",&t10);
for(i10=1;i10<=t10;i10++)
{
    scanf("%lld",&m[i10]);
    scanf("%lld",&n[i10]);
    if(n[i10]>maxi) maxi=n[i10];
}
for(i=1;i*i<=maxi;i++)
    ;
maxi=i;
pr[1]=2;
nr=1;
for(i=3;i<=maxi&&i*i<=maxi;i=i+2)
    if(a[i]==0)
    {
        nr++;
        pr[nr]=i;
        for(j=i*i;j<=maxi;j=j+i)
            a[j]=1;
        if(i%6==1) i=i+2;
    }
for(i=i;i<=maxi;i=i+2)
    if(a[i]==0)
    {
        nr++;
        pr[nr]=i;
        if(i%6==2) i=i+2;
    }
for(i10=1;i10<=t10;i10++)
{
    aux=n[i10];
    nr1=0;
    for(i=1;i<=nr&&pr[i]*pr[i]<=aux;i++)
        if(aux%pr[i]==0)
        {
            while(aux%pr[i]==0)
                aux=aux/pr[i];
            nr1++;
            d[nr1]=pr[i];
        }
    if(aux!=1)
    {
        nr1++;
        d[nr1]=aux;
    }
    n1=((1<<nr1)-1);
    s=0;
    for(j=1;j<=n1;j++)
    {
        aux=j;
        nr2=0;
        while(aux>0)
        {
            aux=(aux&(aux-1));
            nr2++;
        }
        if(nr2%2==1)
        {
            p=1;
            for(i=0;i<=nr1;i++)
                if((j&(1<<i))>0) p=p*d[i+1];
            s=s+m[i10]/p;
        }
        else
        {
            p=1;
            for(i=0;i<=nr1;i++)
                if((j&(1<<i))>0) p=p*d[i+1];
            s=s-m[i10]/p;
        }
    }
    printf("%lld\n",m[i10]-s);
}
return 0;
}