#include <cstdio>

#define MAX2 1000000
#define MAX3 1000000

using namespace std;
int prime[MAX2];
int h;
int prime2[MAX2];

bool ciur[MAX3];
void ciur1()
{
    long long  i,j,k=0;
    for(i=2; i<=MAX3; i++)
    {
        if(ciur[i]==0)
            for(j=i*i; j<=MAX3; j+=i)
                ciur[j]=1;
    }

    for(i=2; i<=MAX3; i++)
        if(ciur[i]==0)
        {
            prime2[++h]=i;

        }


}
int divprim(int x)
{
    int i=1,k,j=0;
    while(prime2[i]*prime2[i]<x)
    {
        k=0;
        while(x%prime2[i]==0)
        {
            x/=prime2[i];
            k=1;
        }
        if(k==1)
        {
            prime[j++]=prime2[i];
        }
        if(i+1>h)
        {
            break;
        }
        i++;
    }
    if(prime2[i]*prime2[i]==x)
    {
        prime[j++]=prime2[i];
        x=1;
        }
    if(x!=1)
        prime[j++]=x;
    return j;
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    int m,j,k,i,n,nr=1;
    long long prod=1,a,b,s;
    fscanf(fin,"%d",&m);
    ciur1();
    for(int l=1; l<=m; l++)
    {
        fscanf(fin,"%lld%lld",&a,&b);
        n=divprim(b);
        s=0;
        for(i=0; i<(1<<n); i++)
        {
            prod=1;
            nr=0;
            for(j=0; j<n; j++)
            {
                if(i & (1<<j))
                {
                    prod*=prime[j];
                    nr++;

                }
            }
            if(nr%2==0)
                s+=a/prod;
            else
                s-=a/prod;


        }
        fprintf(fout,"%lld\n",s);

    }
    return 0;
}