#include<stdio.h>

#define ll long long
#define PMAX 1000000

ll m,a,b,i,dv,answer,f,t,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,fc=f;
  int semn=1;
  for(i=0;i<pr[0];i++,fc>>=1)
   if(1&fc) {
     prod*=pr[i+1];
     semn=0-semn;
   }
  return semn*prod;
}

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

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

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