#include <bits/stdc++.h>
long long Solve(long long p, long long q) {
  if (p % q != 0) return p;
  std::vector<int> primes;
  long long qq = q;
  for (int i = 2; i <= sqrt(qq); i++) {
    if (qq % i == 0) {
      primes.push_back(i);
      while (qq % i == 0) qq /= i;
    }
  }
  if (qq > 1) primes.push_back(qq);
  std::vector<long long> candidates;
  for (const auto prime : primes) {
    long long pp = p;
    while (pp % q == 0) {
      pp /= prime;
    }
    candidates.push_back(pp);
  }
  return *std::max_element(candidates.begin(), candidates.end());
}
int main() {
  int t;
  std::cin >> t;
  while (t--) {
    long long p, q;
    std::cin >> p >> q;
    std::cout << Solve(p, q) << std::endl;
  }
  return 0;
}
