#include<bits/stdc++.h>
using namespace std;
ofstream out("pinex.out");
ifstream in("pinex.in");
bool eratostene[1000001];
int prim[100000],ct,m,a,b,numar_div,divizor[20],nrelemente,factor;
long long suma;
void back(int k,int nr,int produs)
{if(numar_div-k<nrelemente-nr)return ;
    for(int i=k;i<=numar_div;i++)
{
if(nr==nrelemente)
{
    suma+=(1ll*factor*(a/(produs*divizor[i])));
    //out<<produs*divizor[i]<<endl;

}
    else
    back(i+1,nr+1,produs*divizor[i]);

}

}
int main()
{for(int i=2;i<=1000000;i++)
if(!eratostene[i])
{prim[++ct]=i;
for(int j=2*i;j<=1000000;j+=i)
    eratostene[j]=1;

}
in>>m;
for(int q=1;q<=m;q++)
{in>>a>>b;
numar_div=0,suma=0;
for(int i=1;prim[i]*prim[i]<=b&&i<=ct;i++)
if(b%prim[i]==0)
{divizor[++numar_div]=prim[i];
while(!(b%prim[i]))b/=prim[i];
}
if(b>1)divizor[++numar_div]=b;
  for(int i=1;i<=numar_div;i++)
  {nrelemente=i;
  if(nrelemente%2)factor=1;
  else
  factor=-1;

     back(1,1,1);
      //out<<suma<<" ";
  }

    //for(int i=1;i<=numar_div;i++)out<<divizor[i]<<" ";
    out<<a-suma<<'\n';
}
}