#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long p, q;
    cin >> p >> q;
    set<long long> pos;
    auto work = [&](int i) {
      if (q % i == 0) {
        long long cnt = 0, num = 1;
        while (q % i == 0) {
          cnt++;
          num *= i;
          q /= i;
        }
        long long p2 = p, div_by = 1;
        while (p2 % num == 0) {
          p2 /= i;
          div_by *= i;
        }
        pos.insert(div_by);
      }
    };
    for (long long i = 2; i * i <= q; i++) {
      work(i);
    }
    if (q > 1) {
      work(q);
    }
    assert(pos.size());
    p /= *pos.begin();
    cout << p << endl;
  }
  return 0;
}
