#include <bits/stdc++.h>

using namespace std;

#define i32 int32_t
#define i64 int64_t

#define GUARD(expr) \
  do {              \
    if (!(expr)) {  \
      return 1;     \
    }               \
  } while (0)

bool sieve[1'000'000 + 1];

vector<i32> primes;

i64 solve(i64 a, i64 b) {
  vector<i32> k;
  for (i32 p : primes) {
    if (!(b % p)) {
      for (; !(b % p);) {
        b /= p;
      }
      k.push_back(p);
    }
  }
  if (b > 1) {
    k.push_back(b);
  }
  i64 t{0};
  for (size_t x = 1; x < (size_t{1} << k.size()); ++x) {
    i64 c{1};
    for (size_t i = 0; i < k.size(); ++i) {
      if ((x >> i) & 1) {
        c *= k[i];
        if (c > a) {
          break;
        }
      }
    }
    if (c > a) {
      continue;
    }
    c = a / c;
    if (!__builtin_parity(x)) {
      c = (-c);
    }
    t += c;
  }
  return a - t;
}

int main() {
  sieve[0] = sieve[1] = 1;
  for (i64 p = 2; p * p <= 1'000'000; ++p) {
    if (!sieve[p]) {
      for (i64 q = p * p; q <= 1'000'000; q += p) {
        sieve[q] = 1;
      }
    }
  }
  for (i32 i = 2; i <= 1'000'000; ++i) {
    if (!sieve[i]) {
      primes.push_back(i);
    }
  }
#ifndef LOCAL
  freopen("pinex.in", "r", stdin);
  freopen("pinex.out", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  i64 M;
  GUARD(cin >> M && 1 <= M && M <= 500);
  for (; M--;) {
    i64 A, B;
    GUARD(cin >> A >> B && 1 <= A && A <= INT64_C(1'000'000'000'000'000'000) &&
          1 <= B && B <= INT64_C(1'000'000'000'000));
    cout << solve(A, B) << '\n';
  }
  return 0;
}