#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  long long p, q, x;
  long long best = INT_MAX;
  vector<long long> factors;
  while (t--) {
    cin >> p >> q;
    best = INT_MIN;
    if (p % q != 0) {
      cout << p << '\n';
    } else {
      factors.clear();
      for (long long j = 2; j * j <= q; j++) {
        if (q % j == 0) {
          factors.push_back(j);
          factors.push_back(q / j);
        }
      }
      if (factors.size() == 0) {
        factors.push_back(q);
      }
      for (long long i = 0; i < signed(factors.size()); i++) {
        x = p;
        while (x % q == 0) {
          x /= factors[i];
        }
        best = max(best, x);
      }
      if (best < 0) {
        best = 1;
      }
      cout << best << '\n';
    }
  }
  return 0;
}
