#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
unsigned long long n,q,i,j,d,A,B,t,prod,S,nr,poz,fact,a[1000001],v[100001];
int main()
{
   f>>n;
   a[1]=1;
   a[0]=1;
   for(i=2;i*i<=1000001;i++)
   if(a[i]==0)
       for(d=i*i;d<=1000001;d=d+i)
       a[d]=1;


   for(q=1;q<=n;q++)
   {
       f>>A>>B;
       t=0;
       fact=2;
       S=0;
       while(fact*fact<=B)
       {
           if(a[fact]==0)
           {if(B%fact==0){B=B/fact;t++;v[t]=fact;while(B%fact==0)B=B/fact;}}
           fact++;
       }
       if(B>1){t++;v[t]=B;}

      for(i=1;i<=(1<<t)-1;i++)
      {
       nr=0;
       prod=1;
       for(j=0;j<=t-1;j++)
       {

           if((i&(1<<j))!=0)
           {
               poz=t-j;
              nr++;
             prod=prod*v[t-j];
     // g<<v[t-j]<<" ";
           }
       }
//g<<'\n';
       if(nr%2==0)S=S-A/prod;
       else S=S+A/prod;

      }
   g<<A-S<<'\n';
   }


    return 0;
}