#include <fstream>
#include <cmath>
#define NMAX 1000005
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long i1,m,a,b,p,i,c,d,v[10000],j,nr,s,m1,ciur[NMAX],prim[NMAX],q;
int main()
{
f>>m1;
for(i=2;i<=NMAX;i++)
if(ciur[i]==0)
for(j=i+i;j<=NMAX;j=j+i)
ciur[j]=1;
for(i=2;i<=NMAX;i++) if(ciur[i]==0) prim[++q]=i;
for(i1=1; i1<=m1; i1++)
{
s=0;
f>>a>>b;
d=2;
p=0;
c=b;
for(i=1;i<=q;i++)
if(b%prim[i]==0) {v[++p]=prim[i];while(b%prim[i]==0) b/=prim[i];}
if(b>1) v[++p]=b;
for(i=1; i<(1<<p); i++)
{
nr=0;
m=1;
for(j=0; j<p; j++)
if(i&(1<<j))
{
nr++;
m*=v[j+1];
}
if(nr%2) s+=a/m;
else s-=a/m;
}
g<<a-s<<'\n';
}
return 0;
}