#include<cstdio>
#define sqrtB 1000000
using namespace std;

char v[sqrtB+5];
int pr[200005],fp[200005],ka,cont;

void ciur ()
{
    long long i,j;
    for (i=2; i<sqrtB; i++)
        if (!v[i])
        {
            pr[++ka]=i;
            for (j=i+i; j<sqrtB; j+=i)
                v[j]=1;
        }
}

void fact_primi (int x)
{
    cont=0;
    for (int i=1; pr[i]*pr[i]<=x; i++)
        if (x%pr[i]==0)
        {
            while (x%pr[i]==0)
                x/=pr[i];
            fp[++cont]=pr[i];
        }
    if (x!=1)
        fp[++cont]=x;
}

long long calc (long long x,long long a)
{
    long long i,aux,cst,sum,prod,crt,nr1;
    for (i=1; i<(1<<cont); i++)
    {
        aux=i; nr1=0;
        while (aux)
        {
            if (aux & 1)
                nr1++;
            aux>>=1;
        }
        if (nr1 & 1)
            cst=1;
        else cst=-1;
        aux=i; prod=1; crt=1;
        while (aux)
        {
            if (aux & 1)
                prod*=fp[crt];
            crt++;
            aux>>=1;
        }
        sum+=cst*(a/prod);
    }
    return a-sum;
}

int main ()
{
    int m,i;
    long long a,b;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
    scanf("%d",&m);
    for (i=1; i<=m; i++)
    {
        scanf("%lld%lld",&a,&b);
        fact_primi(b);
        printf("%lld\n",calc(b,a));
    }
    return 0;
}