#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 sum=a,prod,nr;
    for (int i=1; i<(1<<cont); i++)
    {
        nr=0; prod=1;
        for (int j=0; j<cont; j++)
            if ((1<<j) & i)
            {
                prod=1LL*prod*fp[j+1];
                nr++;
            }
        if (nr%2)
            nr=-1;
        else nr=1;
        sum=sum+1LL*nr*(a/prod);
    }
    return 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;
}