#include<fstream>
#include<bitset>
#define maxn 1000005
#define minn 100005
using namespace std;
bitset <maxn> p;
int d[minn],n,sub[minn],m,d1[minn],k,nr;
long long suma,a,produs,b;
ifstream cin("pinex.in");
ofstream cout("pinex.out");

void precalc(){
  for(int i=2; i<maxn; i++)
    if(p[i]==0){
      d1[++k]=i;
      for(int j=i+i; j<maxn; j+=i)
        p[j]=1;
    }
}

void solve(){
  n=0;
  for(int i=1; b>1; i++)
    {
    if(b%d1[i]==0){
      d[++n]=d1[i];
      while(b%d1[i]==0)
        b/=d1[i];    
      }
    if(d1[i]*d1[i]>b&&b>1){
      d[++n]=b;
      b=1;
    }
  }
  for(int j=1; j<(1<<n); j++){
     produs=1;nr=0;
     for(int k=0; k<n; k++)
	if(j&(1<<k)){
	  produs*=d[k+1];  
	  nr++;
	}
	if(nr%2==0) nr=-1;
	else nr=1;
	suma+=(a/produs*nr);
  }
}

int main(){
  precalc();
  cin>>m;
  while(m--){ 
    cin>>a>>b;
    solve();
    cout<<a-suma<<'\n';
    suma=0;
  }
  return 0;
}