#include <bits/stdc++.h>
using namespace std;
vector<long long> getPrimes(long long n) {
  vector<long long> v;
  for (long long i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      v.push_back(i);
      n /= i;
    }
  }
  if (n > 1) v.push_back(n);
  return v;
}
void solve() {
  long long p, q;
  cin >> p >> q;
  if (p % q != 0)
    cout << p;
  else {
    vector<long long> v = getPrimes(q);
    sort(v.begin(), v.end());
    long long ans = 1;
    for (long long it : v) {
      long long p2 = p;
      long long cnt = 0;
      while (p2 % it == 0) {
        p2 /= it;
        if (p2 % q != 0) ans = max(ans, p2);
        cnt++;
      }
      ans = max(ans, p2);
    }
    cout << ans;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
}
