#include <iostream>

#define MAXN 1000000

using namespace std;

int primes[MAXN];
int primesSize;
bool ciur[MAXN + 1];
long long d[MAXN];
int divSize;
long long ans;

void precalcPrimes() {
  int i, i2;

  primesSize = 0;
  ciur[1] = true;
  for ( i = 2; i <= MAXN; i++ ) {
    if ( !ciur[i] ) {
      primes[primesSize] = i;
      primesSize++;
      for ( i2 = i * 2; i2 <= MAXN; i2 += i ) {
        ciur[i2] = true;
      }
    }
  }
}

void bkt(long long m, int nrUsed, int pos, long long val, bool use) {
  int sign;

  if ( use ) {
    sign = 1;
    if ( nrUsed % 2 == 0 )
      sign = -1;

    ans = ans + sign * m / val;
  }
  if ( pos == divSize )
    return;

  bkt(m, nrUsed, pos + 1, val, false);
  bkt(m, nrUsed + 1, pos + 1, (long long) val * d[pos], true);
}

long long solve(long long n, long long m) {
  int i;

  i = 0;
  divSize = 0;
  while ( (long long) primes[i] * primes[i] <= n ) {
    if ( (long long) n % primes[i] == 0 ) {
      d[divSize] = primes[i];
      divSize++;
      while ( n % primes[i] == 0 )
        n /= primes[i];
    }
    i++;
  }
  if ( n > 1 ) {
    d[divSize] = n;
    divSize++;
  }
  ans = 0;
  bkt(m, 0, 0, 1, false);

  return m - ans;
}

int main() {
  FILE *fin, *fout;
  fin = fopen("pinex.in", "r");
  fout = fopen("pinex.out", "w");

  int t;
  long long n, m;

  fscanf(fin, "%d", &t);
  precalcPrimes();

  while ( t-- ) {
    fscanf(fin, "%lld%lld", &n, &m);

    fprintf(fout, "%lld\n", solve(m, n));
  }
  return 0;
}