#include <bits/stdc++.h>
using namespace std;
string __fname = "pinex"; ifstream in (__fname + ".in"); ofstream out (__fname + ".out"); 
#define cin in 
#define cout out
const int maxb = 1e6 + 2;
bitset <maxb> sieve;
vector <int> primes;

void solve(int id){
  long long a,b;
  cin >> a >> b;
  vector <int> p;
  for (long long i: primes) {
    if (i * i > b) break;
    if (b % i == 0) {
      p.push_back(i);
      while (b % i == 0) b/=i;
    }
  }
  if (b > 1) p.push_back(b);
  int n = p.size();
  long long rs = 0;
  for (int i = 1; i < (1 << n); i++) {
    long long prod = 1, bts = 0;
    for (int j = 0; j < n; j++){
      if (i & (1 << j)) {
        prod*=p[j];
        bts++;
      }
    }
    if (bts % 2 == 1) rs+=a / prod;
    else rs-=a / prod;
  }
  cout << a - rs << "\n";
  return;
}


int main(){
  for (int i = 2; i < maxb; i++){
    if (!sieve[i]) primes.push_back(i);
    for (int j = i * 2; j < maxb; j+=i) sieve[j] = 1;
  }
  int q;
  cin >> q;
  while (q--) solve(q);
  return 0;
}