#include<stdio.h>

#define ll long long
#define PMAX 1000000

ll a,b,m,i,dv,answer;
ll p[80000],pr[20];
bool isPrime[PMAX],f[20],continuare;

void numerePrime() {
  int i,j;
  for(i=2;i<PMAX;i++) isPrime[i]=1;
  for(i=2;i<PMAX;i++)
   if(isPrime[i]) {
     p[++p[0]]=i;
     for(j=2*i;j<PMAX;j+=i) isPrime[j]=0;
   }
}

void generare() {
  int k;
  for(k=pr[0];k>0 && f[k];k--);
  if(k) {
    f[k]=1;
    for(++k;k<=pr[0];k++) f[k]=0;
  }
  else continuare=0;
}

int main() {
  freopen("pinex.in","r",stdin);
  freopen("pinex.out","w",stdout);
  scanf("%lld",&m);
  numerePrime();
  while(m--) {
    scanf("%lld%lld",&a,&b);

    answer=0;

    pr[0]=0;
    for(i=1;i<=p[0] && b!=1;i++)
     if(!(b%p[i])) {
       f[++pr[0]]=0;
       pr[pr[0]]=p[i];
       dv=p[i];
       while(!(b%(dv*p[i]))) dv*=p[i];
       b/=dv;
     }
    if(b!=1) {
      f[++pr[0]]=0;
      pr[pr[0]]=b;
    }

    continuare=1;
    generare();
    do {
      b=0;
      dv=1;
      for(i=1;i<=pr[0];i++)
       if(f[i]) {
         ++b;
         dv*=pr[i];
       }
      if(b%2) answer+=a/dv;
      else answer-=a/dv;
      generare();
    } while(continuare);
    printf("%lld\n",a-answer);
  }
  return 0;
}