#include <bits/stdc++.h>
using uint = unsigned int;
using cat = long long;
using dbl = long double;
constexpr dbl pi = 3.14159265358979323846;
using namespace std;
template <typename T>
T abs(T x) {
  return (x < 0) ? (-x) : x;
}
cat pw(cat a, cat e, cat mod) {
  if (e <= 0) return 1;
  cat x = pw(a, e / 2, mod);
  x = x * x % mod;
  return (e & 1) ? x * a % mod : x;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  int T;
  cin >> T;
  while (T--) {
    cat P, Q;
    cin >> P >> Q;
    cat tmp = Q;
    static vector<cat> pr;
    pr.clear();
    for (cat r = 2; r * r <= tmp; r++)
      if (tmp % r == 0) {
        while (tmp % r == 0) tmp /= r;
        pr.push_back(r);
      }
    if (tmp > 1) pr.push_back(tmp);
    cat ans = 1;
    for (auto p : pr) {
      int eP = 0, eQ = 0;
      tmp = Q;
      while (tmp % p == 0) tmp /= p, eQ++;
      tmp = P;
      while (tmp % p == 0) tmp /= p, eP++;
      if (eP >= eQ) {
        for (int i = 0; i < eQ - 1; i++) tmp *= p;
        ans = max(ans, tmp);
      } else
        ans = P;
    }
    cout << ans << "\n";
  }
}
