#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
vector<long long> prime;
int vis[N + 10];
long long qpow(long long a, long long b) {
  long long ans = 1, base = a;
  while (b) {
    if (b & 1) {
      ans *= base;
    }
    base *= base;
    b >>= 1;
  }
  return ans;
}
void getprime() {
  for (int i = 2; i <= N; ++i) {
    if (!vis[i]) {
      prime.push_back(i);
    }
    for (long long p : prime) {
      long long v = p * i;
      if (v > N) break;
      vis[v] = 1;
      if (i % p == 0) break;
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  int tt;
  cin >> tt;
  getprime();
  while (tt--) {
    vector<pair<long long, long long> > qyin;
    long long p, q;
    cin >> p >> q;
    if (p % q > 0) {
      cout << p << '\n';
      continue;
    }
    for (long long v : prime) {
      if (q % v == 0) {
        long long cnt = 0;
        while (q % v == 0) {
          q /= v;
          ++cnt;
        }
        qyin.push_back({v, cnt});
      }
    }
    if (q > 1) {
      qyin.push_back({q, 1});
    }
    long long ans = 0;
    for (auto& v : qyin) {
      long long tp = p;
      while (tp % v.first == 0) {
        tp /= v.first;
      }
      tp *= qpow(v.first, v.second - 1);
      ans = max(ans, tp);
    }
    cout << ans << '\n';
  }
}
