#include <bits/stdc++.h>
using namespace std;
long long p, q;
long long fun(long long i) {
  if (i == 1) return 1;
  long long t = p;
  while (t % q == 0) t /= i;
  return t;
}
int main() {
  long long t;
  cin >> t;
  while (t--) {
    cin >> p >> q;
    if (p % q)
      cout << p << endl;
    else {
      long long ans = 1;
      for (long long i = 1; i * i <= q; i++)
        if (q % i == 0) {
          ans = max(ans, max(fun(i), fun(q / i)));
        }
      cout << ans << endl;
    }
  }
}
