#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
bool ok[1000005];
int pr[80005],k=0,dv=0;
long long a,b,d[1005];

void GenPrimes()
{ int i,j,vmax=1000000;
   for(i=2;i<=vmax;i++)
    { if (!ok[i])
       {k++; pr[k]=i;
         for(j=i+i;j<=vmax;j+=i)
          ok[j]=1;
       }
    }
}

void Desc(long long x)
{ int i;
    dv=0;
   for(i=1;i<=k && x>1;i++)
    {if (x%pr[i]==0)
       { dv++; d[dv]=pr[i];
         while(x%pr[i]==0) x/=pr[i];
       }
     if (1LL*pr[i]*pr[i]>1LL*x) break;
    }
 if (x>1) {dv++; d[dv]=1LL*x;}

}

long long Ans()
{ int i,j,num=0;
  long long mult=0,sol=0;

  for(i=1;i<(1<<dv);i++)
  { num=0; mult=1;
     for(j=0;j<dv;j++)
      if (i&(1<<j)) {mult*=1LL*d[j+1]; num++;}
    if (num%2==1) sol+=1LL*(a/mult);
     else sol-=1LL*(a/mult);
  }

 return 1LL*(a-sol);
}


int main()
{ int t;
    GenPrimes();

    f>>t;

   for(;t;t--)
    { f>>a>>b;
      Desc(b);
       g<<Ans()<<"\n";

    }
    return 0;
}