#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 14;
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    long long p;
    int q;
    cin >> p >> q;
    if (p % q) {
      cout << p << '\n';
      continue;
    }
    long long ans = 1;
    auto handle = [&](int i) {
      long long cp = p, mul = 1;
      while (q % i == 0 && q / i % i == 0) {
        q /= i;
        mul *= i;
      }
      q /= i;
      while (cp % i == 0) cp /= i;
      ans = max(ans, cp * mul);
    };
    for (int i = 2; i * i <= q; i++)
      if (q % i == 0) handle(i);
    if (q > 1) handle(q);
    cout << ans << '\n';
  }
}
