#include <iostream>
#include <fstream>

using namespace std;

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

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;
  for (int i = 1; i <= n; i++) {
    fin >> a >> b;
    d = 2; nfp = 0;
    do {
      if (b % d == 0) {
        fp[++nfp] = d;
        do {
          b = b / d;
        } while (b % d == 0);
      }
      if (d == 2)
        d++;
      else
        d += 2;
    } while (b > 1 and d * 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;
}