#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    long long int p, q;
    cin >> p >> q;
    if (p % q)
      cout << p << endl;
    else {
      long long int k = sqrt(q), i = 2, x = q;
      vector<pair<long long int, int> > prime;
      while (i <= k) {
        int count = 0;
        while (x % i == 0) {
          x = x / i;
          count++;
        }
        if (count) prime.push_back(make_pair(i, count));
        i++;
      }
      if (x > 1) prime.push_back(make_pair(x, 1));
      vector<int> count(prime.size());
      x = p;
      for (int i = 0; i < prime.size(); i++) {
        while (x % prime[i].first == 0) {
          count[i]++;
          x = x / prime[i].first;
        }
      }
      int n = prime.size();
      long long int res = 0;
      for (int i = 0; i < prime.size(); i++) {
        int k = count[i] - prime[i].second + 1;
        x = pow(prime[i].first, k);
        res = max(res, p / x);
      }
      cout << res << endl;
    }
  }
  return 0;
}
