#include <iostream>
#include <vector>

using namespace std;

inline void Init (vector < int > &prime) {
  
  int index = 0;
  vector < bool > used (1e6 + 8);
  for (int i = 2; i <= 1e6 + 7; ++ i) {
    if (used[i]) {
      continue;
    }

    used[i] = true;
    prime[++ index] = i;
    for (int j = i * 2; j <= 1e6 + 7; j += i) {
      used[j] = true;
    }
  }
}

inline void Get_primes (long long b, vector < int > &prime, vector < long long > &cur_primes) {

  for (int i = 1; 1ll * prime[i] * prime[i] <= b; ++ i) {
    if (b % prime[i]) {
      continue;
    }

    while (b % prime[i] == 0) {
      b /= prime[i];
    }
    cur_primes.emplace_back (prime[i]);
  }

  if (b != 1) {
    cur_primes.emplace_back (b);
  }
}

inline void Solve (long long nr, int cur, int how_many, long long a, vector < long long > &cur_primes, long long &to_subtract) {

  if (cur == cur_primes.size ()) {
    return;
  }
  
  long long next_nr;
  for (int i = cur; i < (int) cur_primes.size (); ++ i) {

    next_nr = nr * cur_primes[i];
    if (next_nr > a) {
      break;
    }

    if (how_many) {
      to_subtract += (a / next_nr);
    }
    else {
      to_subtract -= (a / next_nr);
    }
    
    Solve (next_nr, i + 1, (how_many + 1) % 2, a, cur_primes, to_subtract);
  }
}

int main () {

  ios::sync_with_stdio(false);

  freopen ("pinex.in", "r", stdin); 
  //FISIERE !!
  freopen ("pinex.out", "w", stdout);
  
  
  int m;
  cin >> m;
  
  vector < int > prime (78507);
  Init (prime);
  
  vector < long long > cur_primes;
  cur_primes.reserve (50);

  while (m --) {
  
    cur_primes.clear();
    long long a, b;
    cin >> a >> b;
    
    long long to_subtract = 0;
    Get_primes (b, prime, cur_primes);

    Solve (1, 0, 1, a, cur_primes, to_subtract);
    cout << a - to_subtract << '\n';
  }
}