#include<stdio.h>
#include<math.h>

#define ll long long
#define PMAX 1000000

ll m,a,b,i,dv,answer,f,t,rad,p[80000],pr[30];
bool isPrime[PMAX];

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

ll produs() {
  ll prod=1;
  int semn=1;
  for(i=0;i<pr[0];i++)
   if(1&(f>>i)) {
     prod*=pr[i+1];
     semn=0-semn;
   }
  return prod*semn;
}

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

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

    answer=a;
    t=1<<pr[0];
    for(f=1;f<t;f++) answer+=a/produs();
    printf("%lld\n",answer);
  }
  return 0;
}