#include <fstream>
#include <vector>

using namespace std;

const int VALMAX = 1e6;

bool compus[VALMAX + 1];

vector<int> prime;
vector<int> primeB;

long long sol, a, b, produs;
void ciur(){
  compus[0] = true;
  compus[1] = true;

  for (int i = 2; i <= VALMAX; i++){
    if (!compus[i]){
      prime.emplace_back(i);
      for (long long j = 1ll * i * i; j <= VALMAX; j += i)
        compus[j] = true;
    }
  }
}

void bkt(int index, int nrElemLuate){
  if (index == primeB.size()){
    if (nrElemLuate != 0){
      if (nrElemLuate % 2 == 1)
        sol += a / produs;
      else
        sol -= a / produs;
    }
    return;
  }

  produs *= primeB[index];
  bkt(index + 1, nrElemLuate + 1);
  produs /= primeB[index];
  bkt(index + 1, nrElemLuate);
}

int main(){

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

  int m;
  fin >> m;

  ciur();

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

    primeB.clear();
    for (int i = 0; i < prime.size(); i++){
      if (b % prime[i] == 0){
        while (b % prime[i] == 0)
          b /= prime[i];
          primeB.emplace_back(prime[i]);
      }
    }

    if (b > 1)
      primeB.emplace_back(b);

    sol = 0;
    produs = 1;

    bkt(0, 0);

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

  return 0;
}