#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int t, p, q, req, i, p1, q1, o, j;
  cin >> t;
  while (t--) {
    cin >> p >> q;
    vector<long long int> v;
    p1 = p;
    q1 = q;
    req = 1;
    for (i = 2; i <= sqrt(q1); i++) {
      if (q1 % i == 0) v.push_back(i);
      while (q1 % i == 0) q1 /= i;
    }
    if (q1 > 1) v.push_back(q1);
    for (i = 0; i < v.size(); i++) {
      p1 = p;
      q1 = q;
      o = 0;
      while (q1 % v[i] == 0) {
        o++;
        q1 /= v[i];
      }
      while (p1 % v[i] == 0) p1 /= v[i];
      for (j = 0; j < o - 1; j++) p1 *= v[i];
      req = max(req, p1);
    }
    if (p % q != 0)
      cout << p << "\n";
    else
      cout << req << "\n";
  }
}
