#include <algorithm>
#include <cstdio>
#include <cmath>
#define N 1000000
using namespace std;

long long a,b,divi[1000],nr,sol;
bool prim[N+100];       ///prim[i]=0 <=> i e prim

void Read()
{
    scanf("%lld%lld",&a,&b);
    nr=0;sol=0;
}

void Ciur(long long val)
{
    int i,j;

    for (i=1;i<val;++i) prim[i]=0;

    if (b%2==0)
    {
        divi[nr++]=2;
        while (b%2==0) b/=2;
    }

    for (i=4;i<val;i+=2)
        prim[i]=1;

    for (i=3;i<val && b>1;i+=2)
        if (!prim[i])
        {
            for (j=i*i;j<val && b>1;j+=2*i)
                prim[j]=1;
            if (b%i==0)
            {
                divi[nr++]=i;
                while (b%i==0) b/=i;
            }
        }
    if (b>1) divi[nr++]=b;
}

void Solve()
{
    long long fact,i,j,biti;

    for (i=1;i<(1<<nr);++i)
    {
        fact=1;biti=0;
        for (j=0;j<nr;++j)
            if (i & (1<<j))
            {
                fact*=1LL*divi[j];
                biti++;
            }
        if (biti%2==0) sol-=1LL*a/fact;
        else sol+=a/fact;
    }
}

void Write()
{
    printf("%lld\n",a-sol);
}

int main()
{
    int t,rad;

    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    scanf("%d",&t);

    while (t--)
    {
        Read();
        rad=sqrt(b)+1;
        Ciur(min(rad,N));
        Solve();
        Write();
    }
    return 0;
}