#include<iostream.h>
#include<fstream.h>
#include<math.h>
#define N 1000000
unsigned long long a,b,s,w,prod;
long x[N],k,j,l,y[N],st[N],r,p,t,q,o;
int m,i,z[N]={0};

int valid(long st[N],long t)
{long i;
for(i=1;i<t;i++)
if(st[i]==st[t])
       return 0;
return 1;}

void sieve(long x[N],long *k,int p[N])
{long i,j;
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;}

int main()
{ifstream f1("pinex.in");
ofstream f2("pinex.out");
f1>>m;
k=0;
sieve(x,&k,z);
for(i=1;i<=m;i++)
       {f1>>a>>b;
       j=1;
       w=b;
       l=0;
       while(w>1&&x[j]<=w/2)
              {o=0;
              while(w%x[j]==0)
                      {o++;
                      w/=x[j];}
              if(o!=0)
                      y[++l]=x[j];
              j++;}
       if(w>1)
              y[++l]=w;
       s=a;
       if(l>0)
              {for(p=1;p<=l;p++)
                     s=s-(a/y[p]);
              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+(a/prod);
                                                    else
                                                            s=s-(a/prod);}
                                             else
                                                    {t++;
                                                    st[t]=st[t-1];}
                                     else
                                             t--;}}}
       f2<<s<<endl;}
f1.close();
f2.close();
return 0;}