#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long b,i,j,p[1000003],a[1000003],s,nr,nre,aa,pp,x;
int short nrd,tt,t;
bool ok;
int main()
{
    f>>tt;nr=1;
    p[1]=2;
     for(i=3;i<=1000000;++i)
    {
      ok=true;
      for(j=1;j<=nr && ok && p[j]*p[j]<=i;j++)
      if(i%p[j]==0) {ok=false;break;}
      if(ok) p[++nr]=i;
    }



    for(t=1;t<=tt;++t)
   { nrd=0;s=0;
   f>>aa>>b;
    for(i=1;i<=nr && b>1;++i)
    { ok=false;
    while(b%p[i]==0)
    {
      b/=p[i];
      ok=true;
    }
    if(ok) a[++nrd]=p[i];
    }
    if(b>1) a[++nrd]=b;

    for(i=1;i<=(1<<nrd)-1;++i)
    {
      x=i;pp=1;nre=0;
      for(j=1;j<=nrd;++j)
      {
        if(x%2==1) {pp*=a[j];++nre;}
        x/=2;
      }

      if(nre%2==1) s+=aa/pp;
      else s-=aa/pp;
    }
     g<<aa-s<<'\n';
   }





    return 0;
}