#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");

long long n,m,v[10001],prm[10001],nrprim=1,nr,sum,q,pr=1,cn,i,j;
bool b[10000];
bool verif[1000000];
int ok=1;




void div()
{int i;
 for(i=1;n!=1&&prm[i]*prm[i]<=n;i++)
   if(n%prm[i]==0){int u=prm[i];
                   v[++nr]=u;
                   while(n%u==0)n/=u;
                  }
 if(n!=1)v[++nr]=n;
}

void afis()

{
 sum+=m/(pr*ok);
 ok=-ok;
}
void backprod(int k)
{
 for(int i=1;i<=nr;i++)
	if(!b[i]&&i>=k){b[i]=1;pr*=v[i];
                    afis();
	                backprod(i);
                    b[i]=0;pr/=v[i];
                   }
}

int main()
{prm[1]=2;
 for(i=3;i<=1000000;i+=2)
  if(!verif[i]){prm[++nrprim]=i;
                for( j=i;j<=1000000;j+=i)verif[j]=1;
               }
for(i=1;i<=1000000;i++)b[i]=0;
f>>q;
 while(f>>m>>n)
 {nr=0;sum=0;pr=1;ok=1;
  div();
  backprod(1);
  g<<m-sum<<'\n';
 }
 return 0;

}