#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int n,q,i,j,A,B,t,prod,S,nr,poz,fact,v[10001];
int main()
{
   f>>n;
   for(q=1;q<=n;q++)
   {
       f>>A>>B;
       t=0;
       fact=2;
       S=0;
       while(fact*fact<=B)
       {
           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;
}