#include <fstream>
#define maxV 2000003
#define ll long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int n,m,p[maxV/9];
ll a,b,sol,d[102];
bool w[maxV];
void primes()
{
   int i,j;
   w[1]=1;
   for(i=2;i<maxV;++i)
      if(!w[i])
      {
          p[++p[0]]=i;
          if(i<1500)
            for(j=i*i;j<maxV;j+=i) w[j]=1;
      }
}
void desc(ll x)
{
   int i;
   sol=a;
   d[0]=0;
   for(i=1;p[i]*p[i]*1LL<=x;++i)
       if(x%p[i]==0)
    {
        while(x%p[i]==0) x/=p[i];
        d[++d[0]]=p[i];
    }
    if(x!=1LL) d[++d[0]]=x;
}
void solve()
{
   int i,j,nb1;
   ll p;
   desc(b);
   for(i=1;i<(1<<d[0]);++i)
   {
       nb1=0;
       p=1LL;
       for(j=0;j<d[0];++j)
           if(i&(1<<j))
        {
            ++nb1;
            p*=d[j+1];
        }
        if(nb1&1) sol-=(a/p);
        else sol+=(a/p);
   }
}
int main()
{
    f>>m;
    primes();
    while(m--)
    {
        f>>a>>b;
        solve();
        g<<sol<<'\n';
    }
    return 0;
}