#include <bits/stdc++.h>
using namespace std;
const long long MOD = (long long)1e9 + 7;
map<long long, long long> prime_factor(long long n) {
  map<long long, long long> res;
  for (long long i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ++res[i];
      n /= i;
    }
  }
  if (n != 1) res[n] = 1;
  return res;
}
signed main() {
  long long T;
  cin >> T;
  while (T--) {
    long long p, q;
    cin >> p >> q;
    if (p % q != 0) {
      cout << p << endl;
      continue;
    }
    map<long long, long long> mp = prime_factor(q);
    long long ans = 0;
    for (auto it : mp) {
      long long d = it.first;
      long long x = p;
      long long cnt = 0;
      while (x % d == 0) {
        x /= d;
        cnt++;
      }
      for (long long i = 0; i < it.second - 1; i++) x *= d;
      ;
      ans = max(ans, x);
    }
    cout << ans << endl;
  }
}
