#include<fstream.h>
#include<math.h>
#define N 1000000
unsigned long long a,b,s,w,h,x[N],y[N];
long k=1,j,l,u[N],r,p[N],t,q,o,z;
int m,i;
int v(long u[N],long t)
{for(j=1;j<t;j++)
if(u[j]==u[t])
      return 0;
return 1;}
int main()
{ifstream f("pinex.in");
ofstream g("pinex.out");
f>>m;
x[k]=2;
for(i=1;((i*i)<<1)+(i<<1)<=N;i++)     
if(!(p[i>>3]&(1<<(i&7))))
      for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=N;j+=(i<<1)+1)
               p[j>>3]|=(1<<(j&7));
for(i=1;2*i+1<=N;i++)
if(!(p[i>>3]&(1<<(i&7))))
      x[++k]=2*i+1;
while(m--)
      {f>>a>>b;
      l=0;
      for(j=1,w=b;w>1&&x[j]<=sqrt(w);j++)
            {o=0;
            while(w%x[j]==0)
                   o++,w/=x[j];
            if(o)
                   y[++l]=x[j];}
      if(w>1)
            y[++l]=w;
      s=a;
      if(l>0)
            {for(z=1;z<=l;z++)
                  s=s-(unsigned long long)(a/y[z]);
            for(r=2;r<=l;r++)
                  {t=1,u[t]=0;
                  while(t>0)
                         {u[t]++;
                         if(v(u,t))
                                 if(u[t]<=l)
                                          if(t==r)
                                                  {h=1;
                                                  for(q=1;q<=r;q++)
                                                           h*=y[u[q]];
                                                  if(r%2==0)
                                                           s=s+(unsigned long long)(a/h);
                                                  else
                                                           s=s-(unsigned long long)(a/h);}
                                          else
                                                  t++,u[t]=u[t-1];
                                 else
                                          t--;}}}
      g<<s<<"\n";}
return 0;}