#include<fstream>
using namespace std;
ifstream f("pinex.in"); ofstream g("pinex.out");
char w[1000011]; //w[i] == 0 daca i este prim
long long a,b,sum,s,d[30],p[100001];
int T,n,i,k,nr=0,m,x[30];
void ciur()
{int i,j;
 for(i=2; i<=1000000; i++)
  if(!w[i])
   {p[++nr]=i;
    for(j=i+i; j<=1000000; j+=i) w[j]=1;
   };
}
void prelsol()
{int i; long long pr=1;
 for(i=1; i<=n; i++) pr=pr*d[x[i]];
 s+=a/pr;
}
void back()
{s=0; k=1; x[k]=0;
 do {while(x[k]<m-n+k)
        {x[k]++;
         if(k==n) prelsol(); 
          else {k++; x[k]=x[k-1];};
        }
     k--;
    }
 while(k); 
 if(n%2) sum+=s; else sum-=s;
} 
int main()
{ciur();
 f>>T;
 while(T--)  
   {f>>a>>b;
    m=0; i=1;
    while(b>1 && p[i]*p[i]<=b)
      {if(b%p[i]==0)
          {d[++m]=p[i];
           while(b%p[i]==0) b/=p[i];
          };
        i++;
      }
    if(b>1) d[++m]=b;
    sum=0; 
    for(n=1; n<=m; n++) back();
    g<<a-sum<<'\n';  
   }
 g.close(); return 0;
}