#include <bits/stdc++.h>
using namespace std;
long long p[101010];
void testi() {
  long long p, q;
  cin >> p >> q;
  if (p % q != 0) {
    cout << p << "\n";
    return;
  }
  multiset<long long> s;
  for (long long i = 2; i <= 100000; ++i) {
    while (q % i == 0) {
      s.insert(i);
      q /= i;
    }
  }
  long long ans = 0;
  if (q > 1) s.insert(q);
  for (auto u : s) {
    long long a = s.count(u);
    long long b = p;
    while (b % u == 0) {
      b /= u;
    }
    for (long long i = 1; i <= a - 1; ++i) {
      b *= u;
    }
    ans = max(ans, b);
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (long long i = 2; i <= 100000; ++i) {
    if (p[i]) {
      for (long long j = i * 2; j <= 100000; j += i) p[j] = i;
    }
  }
  int t;
  cin >> t;
  while (t--) testi();
}
