#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,d[1005],sum,a,b;

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(int 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 (pr[i]*pr[i]>x) break;
    }
 if (x>1) {dv++; d[dv]=x;}

}

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

  for(i=1;i<(1<<dv);i++)
  { sum=0; 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+=a/mult;
     else sol-=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;
}