#include<cstdio>
#include<cmath>
#include<bitset>
#define NMAX 1000000
using namespace std;
int m,i,j,k;
long long a,b,fact[100];
int t=0,d=0;
int v[NMAX];
bitset<NMAX>viz;
void ciur()
{
    k=0;
    for (i=2;i<NMAX;++i)
    {
        if (viz[i]==0)
        {
            v[++k]=i;
            for (j=2;j*i<NMAX;++j)
                viz[i*j]=1;
        }
    }
}
void divizor()
{
    t=0,d=0;
    while (b>1)
    {
        d++;
        if (b%v[d]==0)
        {
            fact[++t]=v[d];
            while (b%v[d]==0) b/=v[d];
        }
        if (v[d]>sqrt((double)b) && b>1)
        {
            fact[++t]=b;
            b=1;
        }
    }
}
void calc()
{
    long long sol=a;
    for (int i=1;i<(1<<t);i++)
    {
        long long nr=0,prod=1;
        for (int j=0;j<t;j++)
            if ((1 << j) & i)
            {
                prod=1LL*prod*fact[j+1];
                nr++;
            }

        if (nr%2) nr=-1;
        else nr=1;
        sol=sol+1LL*nr*a/prod;
    }
    printf("%lld\n",sol);
}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&m);
    ciur();
    for (i=1;i<=m;++i)
    {
        scanf("%lld%lld",&a,&b);
        divizor();
        calc();
    }
    return 0;
}