#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long p, q;
void read_input() { cin >> p >> q; }
long long func(long long i) {
  if (i == 1) return 0;
  long long n = q, POW = i;
  while (n % i == 0) {
    n /= i, POW *= i;
  }
  long long P = p;
  while (P % i == 0) {
    P /= i;
  }
  return P * (POW / i / i);
}
void solve() {
  if (p % q) {
    cout << p << '\n';
    return;
  }
  long long ans = 0;
  for (long long i = 1; i <= sqrt(q); i++) {
    if (q % i != 0) continue;
    ans = max(ans, max(func(i), func(q / i)));
  }
  cout << ans << '\n';
}
void write_output() {}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    read_input();
    solve();
  }
  return 0;
}
