#include<fstream>
#include<bitset>
#define maxn 1000005
#define minn 100005
using namespace std;
bitset <maxn> p;
int b,d[minn],n,sub[minn],m,d1[minn],k;
long long suma,a,produs;

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 submultimi(int e, int l){
    while(e<=n){
      sub[l]=d[e];
      produs=1;
      for(int i=1; i<=l; i++)
        produs=1LL*produs*sub[i];
      if(l%2==1)
        suma+=1LL*a/produs;
      else suma-=1LL*a/produs;
      submultimi(e+1,l+1);
      e++;
    }
}

void divizori(){
  n=0;
  for(int i=1; d1[i]<=b; i++)
    if(b%d1[i]==0){
      d[++n]=d1[i];
      while(b%d[n]==0)
        b/=d[n];
    }
}

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


/*#include<iostream>
using namespace std;
int n,v[20];

void submultimi(int e, int l){
    while(e<=n){
      v[l]=e;
      for(int i=1; i<=l; i++)
        cout<<v[i]<<' ';
      cout<<'\n';
      submultimi(e+1,l+1);
      e++;
    }
}

int main(){
  cin>>n;
  submultimi(1,1);
  return 0;
}
*/