#include <bits/stdc++.h>
using namespace std;
int main() {
  int64_t t;
  cin >> t;
  while (t--) {
    int64_t p, q;
    cin >> p >> q;
    set<int64_t> s1;
    if (p % q != 0) {
      cout << p << endl;
    } else {
      int64_t ans, p1 = p, q2;
      while (p1 % q == 0) {
        p1 /= q;
      }
      ans = p1;
      for (int64_t i = 2; (i) * (i) <= q; i++) {
        if (q % i != 0) continue;
        q2 = q;
        p1 = p;
        while (p1 % q == 0) {
          p1 = p1 / i;
        }
        ans = max(ans, p1);
        p1 = p;
        int64_t l;
        l = q / i;
        while (p1 % q == 0) {
          p1 = p1 / l;
        }
        ans = max(ans, p1);
      }
      cout << ans << endl;
    }
  }
}
