#include<stdio.h>
#include<math.h>
#define MAX 1000001
long long a,b,fact[50],m,nrfact,sol;
int prime[100000],nrp;
bool comp[MAX];

void NrPrime()
{
    for(int i=2;i<=MAX;i++)
    {
        if(!comp[i])
        {
            prime[++nrp]=i;
            for(int j=2*i;j<=MAX;j+=i)
            {
                comp[j]=1;
            }
        }
    }
}

void descompuneB(long long b)
{
    nrfact=0;
    for(int d=1;prime[d]<=(int)sqrt(b) && b!=1 && d<=nrp; d++)
    {
        if(b%prime[d]==0)
        fact[++nrfact]=prime[d];
        while(b%prime[d]==0)
        b/=prime[d];
    }
    if(b>1)
    {
        fact[++nrfact]=b;
    }
}


void rezolva(long long a,long long b)
{
    descompuneB(b);
    sol=a;
    for(int i=1;i<(1<<nrfact);i++)
    {
        long long prod=1,nr=0;
        for(int j=0;j<nrfact;j++)
        {
            if(i&(1<<j))
            {
                prod*=fact[j+1];
                nr++;
            }
        }
        if(nr%2==1)
        {
            sol-=a/prod;
        }
        else
        sol+=a/prod;
    }
    printf("%I64d\n",sol);
}

void citire()
{
    freopen("pinex.in","r",stdin);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld %lld",&a,&b);
        rezolva(a,b);
    }
}

int main()
{
    freopen("pinex.out","w",stdout);
    NrPrime();
    citire();
    return 0;
}