#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long> > fac;
void init(long long x) {
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      long long cnt = 0;
      while (x % i == 0) x /= i, cnt++;
      fac.emplace_back(i, cnt);
    }
  }
  if (x > 1) fac.emplace_back(x, 1);
}
void solve() {
  long long a, b;
  cin >> a >> b;
  fac.clear();
  init(b);
  if (a % b != 0) {
    cout << a << '\n';
    return;
  }
  long long ans = 1;
  for (auto &pq : fac) {
    long long f = pq.first, k = pq.second, x = a, res = 1;
    for (long long i = 0; i < k - 1; i++) res *= f;
    while (x % f == 0) x /= f;
    ans = max(ans, x * res);
  }
  cout << ans << '\n';
}
signed main() {
  long long T;
  cin >> T;
  while (T--) solve();
  return 0;
}
