#include <bits/stdc++.h>
using namespace std;
template <class T>
bool tmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool tmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
void setIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
long long P, Q;
long long p, q, r;
bool upd(long long pr) {
  int fp = 0, fq = 0;
  while (q > 1 && q % pr == 0) {
    ++fq;
    q /= pr;
  }
  if (fq == 0) return false;
  while (p > 1 && p % pr == 0) {
    ++fp;
    p /= pr;
  }
  if (fq > fp) return true;
  long long rr = 1;
  for (int _n(fp - fq + 1), i(0); i < _n; i++) rr *= pr;
  r = min(r, rr);
  return false;
}
long long solve() {
  if (P < Q) return P;
  r = P;
  p = P;
  q = Q;
  if (upd(2)) return P;
  for (long long pr = 3; pr * pr <= Q; pr += 2)
    if (upd(pr)) return P;
  if (q > 1 && upd(q)) return P;
  return P / r;
}
int main() {
  setIO();
  int t;
  cin >> t;
  while (t--) {
    cin >> P >> Q;
    cout << solve() << "\n";
  }
  return 0;
}
