#include <fstream>
#include <iostream>
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,p[1000001],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)
       {


       q++;

       p[q]=i;

       for(d=i*i;d<=1000001;d=d+i)
       a[d]=1;
       }


   }


   for(q=1;q<=n;q++)
   {
       f>>A>>B;


       t=0;
       fact=1;
       S=0;
       int copie=B;
       while(p[fact]*p[fact]<=B&&fact<=168)
       {
       //  cout<<fact<<" ";
           if(B%p[fact]==0){B=B/p[fact];t++;v[t]=p[fact];while(B%p[fact]==0){B=B/p[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;
}