#include<fstream.h>
#include<math.h>
#define N 1000000
unsigned long long a,b,s,w,prod,x[N],y[N];
long k=1,j,l,st[N],r,p[N]={0},t,q,o,z;
int m,i;
int valid(long st[N],long t)
{for(long i=1;i<t;i++)
if(st[i]==st[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+=1)     
if((p[i>>3]&(1<<(i&7)))==0)
      {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)))==0)
      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;
                  st[t]=0;
                  while(t>0)
                         {st[t]++;
                         if(valid(st,t)==1)
                                 if(st[t]<=l)
                                          if(t==r)
                                                  {prod=1;
                                                  for(q=1;q<=r;q++)
                                                           prod*=y[st[q]];
                                                  if(r%2==0)
                                                           s=s+(unsigned long long)(a/prod);
                                                  else
                                                           s=s-(unsigned long long)(a/prod);}
                                          else
                                                  t++,st[t]=st[t-1];
                                 else
                                          t--;}}}
g<<s<<"\n";}
f.close();
g.close();
return 0;}