#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000005;

int t;

long long a, b;

int sieve[MAX_N];
vector < int > primes;

int main() {
  freopen("pinex.in", "r", stdin);
  freopen("pinex.out", "w", stdout);
  sieve[0] = sieve[1] = 1;
  for (int i = 2; i * i < MAX_N; ++i) {
    if (sieve[i] == 0) {
      primes.push_back(i);
      for (int j = i * i; j < MAX_N; j += i) {
        sieve[j] = 1;
      }
    }
  }
  scanf("%d", &t);
  while (t --) {
    vector < int > divs;
    divs.clear();
    scanf("%lld %lld", &a, &b);
    for (int i = 0; primes[i] * primes[i] <= b; ++i) {
      if (b % primes[i] == 0) {
        divs.push_back(primes[i]);
        while (b % primes[i] == 0) {
          b /= primes[i];
        }
      }
    }
    if (b > 1) {
      divs.push_back(b);
    }
    long long ans = 0;
    for (int perm = 1; perm < (1 << (int(divs.size()))); ++perm) {
      long long thisPerm = 1;
      int sign = 0;
      for (int j = 0; j < int(divs.size()); ++j) {
        if ((perm & (1 << j)) > 0) {
          thisPerm = 1LL * thisPerm * 1LL * (divs[j]);
          sign ^= 1;
        }
      }
      if (sign > 0) {
        ans = 1LL * ans + 1LL * (a / thisPerm);
      } else {
        ans = 1LL * ans - 1LL * (a / thisPerm);
      }
    }
    printf("%lld\n", a - ans);
  }
  return 0;
}