#include <cstdio>
#define MAXN 1000000
#define MAXP 20

using namespace std;

int prime[MAXN], nr;
int low[MAXN+1], v[MAXP];

inline void ciur(int n){
  int i, j;
  for(i=2; i<=n; i++){
    if(low[i]==0){
      low[i]=i;
      prime[nr++]=i;
    }
    for(j=0; j<nr && prime[j]<=low[i] && prime[j]*i<=n; j++)
      low[prime[j]*i]=prime[j];
  }
}

int main()
{
    FILE *fin, *fout;
    long long a, b, ans, rez;
    int m, i, j, nrp, k, bits;
    fin=fopen("pinex.in", "r");
    fscanf(fin, "%d", &m);
    fout=fopen("pinex.out", "w");
    ciur(MAXN);
    for(i=0; i<m; i++){
      fscanf(fin, "%lld%lld", &a, &b);
      nrp=0;
      for(j=0; j<nr && 1LL*prime[j]*prime[j]<=b; j++)
        if(b%prime[j]==0){
          v[nrp++]=prime[j];
          while(b%prime[j]==0)
            b/=prime[j];
        }
      if(b>1)
        v[nrp++]=b;
      ans=a;
      for(j=1; j<(1<<nrp); j++){
        rez=1LL; bits=0;
        for(k=0; k<nrp; k++)
          if(j&(1<<k)){
            ++bits;
            rez*=1LL*v[k];
          }
        if(bits&1)
          ans-=a/rez;
        else
          ans+=a/rez;
      }
      fprintf(fout, "%lld\n", ans);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}