#include<cstdio>
unsigned long long a,b,s,w,h,x[1000000],y[1000000];
int k=1,j,l,u[1000000],r,p[1000000],t,q,o,z,m,i;

int A(int u[],int t)
{for(j=1;j<t;j++)
if(u[j]==u[t])
      return 0;
return 1;}

int main()
{freopen("pinex.in","r",stdin);
freopen("pinex.out","w",stdout);
scanf("%d",&m),x[k]=2;
for(i=1;((i*i)<<1)+(i<<1)<=1000000;i++)     
if(!(p[i>>3]&(1<<(i&7))))
      for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=1000000;j+=(i<<1)+1)
               p[j>>3]|=(1<<(j&7));
for(i=1;2*i+1<=1000000;i++)
if(!(p[i>>3]&(1<<(i&7))))
      x[++k]=2*i+1;
while(m--)
      {scanf("%llu%llu",&a,&b),l=0;
      for(j=1,w=b;w>1&&x[j]*x[j]<=w;j++)
            {for(o=0;w%x[j]==0;o++,w/=x[j]);
            if(o)
                   y[++l]=x[j];}
      if(w>1)
            y[++l]=w;
      s=a;
      if(l)
            {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)
                         {u[t]++;
                         if(A(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--;}}}
      printf("%llu\n",s);}
return 0;}