#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
int prime[80000];

void gaseste_prime() {
    bool eprim[80000];
    int l = 0, n = 1000000;

    for (int i = 1; i <= 80000; i++) // Presupunem ca toate sunt prime.
      eprim[i] = true;
    for (int d = 2; d <= n; d++)
      if (eprim[d]) {
        prime[++l] = d;
        if (n / d > d)
          for (int m = d * d; m <= n; m += d)
            eprim[m] = false;
      }
}

int main () {
  long long int d = 2; // numarul de factori primi
  int nfp = 0, n, semn;
  long long int fp[20], a, b;
  long long int sol;

  fin >> n;
  gaseste_prime();
  for (int i = 1; i <= n; i++) {
    fin >> a >> b;
    d = 1; nfp = 0;
    do {
      if (b % prime[d] == 0) {
        fp[++nfp] = prime[d];
        do {
          b = b / prime[d];
        } while (b % prime[d] == 0);
      }
      d++;
    } while (b > 1 and prime[d] * prime[d] <= b);
    if (b > 1)
      fp[++nfp] = b;
//      for (int f = 1; f <= nfp; f++)
//        cout << fp[f] << ' ';
    sol = a;
    for (int i = 1; i < (1 << nfp); i++) { // pentru fiecare intersectie de multimi
      long long int nr = 0, prod = 1;
      for (int j = 0; j < nfp; j++) // pentru fiecare factor
        if ((1 << j) & i) {
          prod = prod * fp[j + 1];
          nr++;
        }
      if (nr % 2 == 1)
        semn = -1;
      else
        semn = 1;
      sol = sol + semn * a / prod;
    }
    fout << sol << '\n';
  }
  return 0;
}