#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;
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 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;
}