#include <cstdio>
#define MAX 500
#define MAX2 1000
using namespace std;
int prime[MAX2];
struct pinex
{
    int a;
    int b;
}v[MAX];
int divprim(int x)
{
    int i=2,k,j=1;
    while(i*i<x)
    {
        k=0;
        while(x%i==0)
        {
            x/=i;
            k=1;
        }
        if(k==1)
        {
            prime[j++]=i;
        }
        i++;
    }
    if(i*i==x)
        prime[j++]=i;
    if(x!=1)
            prime[j++]=x;
    return j-1;
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    int m,j,s,k,i;
    fscanf(fin,"%d",&m);
    for(i=1; i<=m; i++)
    {
        fscanf(fin,"%d%d",&v[i].a,&v[i].b);
    }
    for(i=1; i<=m; i++)
    {
        int n;
        s=0;
        n=divprim(v[i].b);
        for(j=1; j<=n; j++)
        {
            s+=v[i].a/prime[j];
        }
        if(n!=1)
        {
        for(j=1; j<=n; j++)
        {
            //  for(k=j+1;k<=n;k++)
            // {
            if(j==n)
            {
                s-=v[i].a/(prime[j]*prime[1]);
            }
            else
                s-=v[i].a/(prime[j]*prime[j+1]);

            //  }
        }
        int s2=1;
        for(j=1;j<=n;j++)
        {
            s2*=prime[j];
        }
        s+=v[i].a/s2;
        }
        fprintf(fout,"%d\n",v[i].a-s);
    }

    return 0;
}