#include <cstdio>
#include <cmath>
using namespace std;
int m,nr,p=1,fact[1000],prim[500002],nrprime[500002];
double rad;
long long a,b,i,j,nrm,nrf,nrp,rasp;
void ciur()
{
nrprime[0]=2;
for (i=1;i<=500000;i++)
if (prim[i]==0)
   {
   nrp++;nrprime[nrp]=2*i+1;
   for (j=2*i*i+2*i;j<=500000;j+=2*i+1)
     prim[j]=1;
   }
}
void calc()
{
int k;
nrm=1<<nrf;nrm--;k=0;
for (i=1;i<=nrm;i++)
   {
   p=1;k=0;
    for (j=0;j<nrf;j++)
      if (i & (1<<j))
         {
         p*=fact[nrf-j];
         k++;
         }
    if (k%2==1) rasp-=a/p;
           else rasp+=a/p;
   }
rasp+=a;
}
int main()
{
freopen("pinex.in","r",stdin);
freopen("pinex.out","w",stdout);
scanf("%d",&m);
ciur();
while (m)
   {
   scanf("%d%d",&a,&b);
   rad=sqrt(b);i=0;
   while (b>1)
      {
       if (b%nrprime[i]==0) {
                            fact[++nrf]=nrprime[i];
                            while (b%nrprime[i]==0) b/=nrprime[i];
                            }
      if (b>1 && nrprime[i]>rad)
        {
         fact[++nrf]=b;
         b=1;
        }
      i++;
      }
   calc();
   printf("%d\n",rasp);
   m--;nrf=0;rasp=0;p=1;
   }
}