#include <cstdio>
#define MAX 500
#define MAX2 1000
#define MAX3 1000000

using namespace std;
int prime[MAX2];
int h;
int prime2[MAX2];
struct pinex
{
    int a;
    int b;
} v[MAX];
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++>h)
        {
            break;
        }
    }
    if(prime2[i]*prime2[i]==x)
        prime[j++]=prime2[i];
    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;
}