#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long a,b,n,i,j,v[1000001],k,t,d,sol,nrc,p;
int main()
{ fin>>t;
  for(k=1;k<=t;k++)
     {fin>>a>>b;
      n=0;
      if(b%2==0)
         {n++;
          v[n]=2;
          while(b%2==0)
               b/=2;
         }
      d=3;
      while(b>1)
      {if(b%d==0)
          {n++;
           v[n]=d;
          }
       while(b%d==0)
             b/=d;
       d+=2;
       if(d*d>b)
          d=b;
      }
      sol=a;
      for(i=1;i<(1LL<<n);i++)
      {nrc=0;
       p=1;
       for(j=0;j<n;j++)
        if(i&(1LL<<j))
           {nrc++;
            p=p*v[j+1];
           }
        if(nrc%2==1)
           sol=sol-a/p;
        else
           sol=sol+a/p;
      }
      fout<<sol;
     }
    return 0;
}