#include <bits/stdc++.h>

using namespace std;

ifstream fin ("pinex.in");
ofstream fout ("pinex.out");

const int NMAX = 1000000;
int prime[NMAX + 2], k, fact[NMAX + 2];
bool f[NMAX + 2];

void ciur () {
  for (int i =4; i <+ NMAX ; i += 2)
    f[i] = 1;
  for (int i = 3; i * i <= NMAX; i += 2)
    if (f[i] == 0)
      for (int j = i * i; j <= NMAX; j += 2 * i)
        f[j] = 1;
  prime[++k] = 2;
  prime[++k] = 3;
  int d = 5;
  while (d <= NMAX) {
    if (f[d] == 0)
      prime[++k] = d;
    if (f[d + 2] == 0)
      prime[++k] = d + 2;
    d += 6;
  }
}

long long n, a, b;

int main() {
  ciur();
  fin >> n;
  for (int t = 1; t <= n; t++) {
    fin >> a >> b;
    int i = 1, k1 = 0;
    while (prime[i] * prime[i] <= b && b > 1) {
      if (b % prime[i] == 0) {
        fact[++k1] = prime[i];
        while (b % prime[i] == 0)
          b /= prime[i];
      }
      i++;
    }
    if (b > 1)
      fact[++k1]= b;
    long long ans = 0;
    for (int i = 1; i < (1 << k1); i++) {
      int nr = 0;
      long long p = 1;
      for (int j = 0; j < k1; j++)
        if (i & (1 << j)) {
          p *= fact[j + 1];
          nr++;
        }
      if (nr % 2)
        ans += (a - 1) / p;
      else
        ans -= (a - 1) / p;
    }
    fout << a - ans - 1 << "\n";
  }
  return 0;
}