#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAX_DIV_PRIMI = 11;
const int MAX_BM = 1 << MAX_DIV_PRIMI;
const int RADB = 1000000;

int nr_biti[MAX_BM + 5];
bool ciur[RADB + 5];
vector<int> prime;

void precalc() {
  for(int bm = 1; bm < MAX_BM; bm++)
    nr_biti[bm] = nr_biti[bm / 2] + bm % 2;

  ciur[0] = ciur[1] = true;
  for(int i = 2; i <= RADB; i++)
    if(!ciur[i]) {
      prime.push_back(i);
      for(int j = 2 * i; j <= RADB; j += i)
        ciur[j] = true;
    }
}

void solve() {
  long long a, b;
  scanf("%lld %lld", &a, &b);

  vector<int> div_primi;
  for(int prim: prime) {
    if((long long)prim * (long long)prim > b)
      break;
    if(b % prim == 0) {
      div_primi.push_back(prim);
      while(b % prim == 0)
        b /= prim;
    }
  }
  if(b > 1)
    div_primi.push_back(b);

  /// calculez toate numerele de forma p1 * p2 * ... * pk, p1 e in div_primi, 1 <= k <= div_primi.size()
  const int nr_dp = div_primi.size();
  const int bm_max = 1 << nr_dp;
  long long neprime = 0;
  for(int bm = 1; bm < bm_max; bm++) {
    long long crt = 1;

    for(int i = 0; i < nr_dp; i++)
      if(bm & (1 << i))
        crt *= (long long)div_primi[i];

    /// daca e un nr par de div primi, scad nr de multipli ai lui crt, altfel ii adun
    neprime += (nr_biti[bm] % 2 == 0 ? -1 : 1) * (a / crt);
  }

  printf("%lld\n", a - neprime);
}

int main() {
  freopen("pinex.in", "r", stdin);
  freopen("pinex.out", "w", stdout);
  int m;

  precalc();

  scanf("%d", &m);
  for(int i = 1; i <= m; i++)
    solve();

  return 0;
}