#include <bits/stdc++.h>

using namespace std;

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

int n, cnt, nr, primi[200000];
long long rezultat, a , b, divizori[12];
bool ciur[1000001];

void eratostene () {
  ciur[1] = ciur[0] = 1;
  for (int i = 2; i * i <= 1000001; i++) {
    if (!ciur[i]) {
      for (int j = i; i * j <= 1000001; j++) {
        ciur[i * j]++;
      }
    }
  }

  for (int i = 2; i <= 1000001; i++) {
    if (!ciur[i]) {
      primi[++cnt] = i;
    }
  }
}

int main () {

  fin >> n;

  eratostene();

  for (int i = 1; i <= n; i++) {
    fin >> a >> b;

    int j = 1;
    nr = 0;
    rezultat = 0;
    while (j <= cnt && primi[j] * primi[j] <= b) {
      if (b % primi[j] == 0) {
        divizori[++nr] = primi[j];

        while (b % primi[j] == 0) {
          b /= primi[j];
        }
      }

      j++;
    }

    if (b > 1) {
      divizori[++nr] = b;
    }

    for (int j = 1; j < (1 << nr); j++) {
      int elemente = 0;
      long long p = 1;


      for (int k = 0; k < nr; k++) {
        if (j & (1 << k)) {
          p *= divizori[k + 1];
          elemente++;
        }
      }

      if (elemente % 2) {
        rezultat += (a / p);
      } else {
        rezultat -= (a / p);
      }
    }


    fout << a - rezultat << '\n';
  }

  return 0;
}