#include <bits/stdc++.h>
using namespace std;
const long long int INF = LLONG_MAX / 2;
int main() {
  long long int t, i, j;
  cin >> t;
  while (t--) {
    long long int p, q;
    cin >> p >> q;
    if (p % q != 0) {
      cout << p << "\n";
      continue;
    }
    vector<pair<long long int, long long int>> fac;
    long long int x = q;
    long long int cnt;
    for (i = 2; i * i <= x; i++) {
      if (x % i == 0) {
        cnt = 0;
        while (x % i == 0) {
          cnt++;
          x /= i;
        }
        fac.push_back({i, cnt});
      }
    }
    if (x != 1) fac.push_back({x, 1});
    long long int ans = (long long int)0;
    long long int common;
    for (auto x : fac) {
      common = p;
      while (common % q == 0) {
        common /= x.first;
      }
      ans = max(ans, common);
    }
    cout << ans << "\n";
  }
  return 0;
}
