#include <bits/stdc++.h>
using ll = long long int;
using namespace std;
int main() {
  ll t;
  cin >> t;
  while (t--) {
    ll p, q;
    cin >> p >> q;
    if (p % q != 0)
      cout << p << "\n";
    else {
      ll x = 1;
      for (ll i = 1; i <= sqrt(q); i++) {
        if (q % i == 0) {
          ll pnew = p;
          while (i != 1 && pnew % i == 0) {
            pnew = pnew / i;
            if (pnew % q != 0) {
              x = max(x, pnew);
              break;
            }
          }
          pnew = p;
          while (pnew % (q / i) == 0) {
            pnew = pnew / (q / i);
            if (pnew % q != 0) {
              x = max(x, pnew);
              break;
            }
          }
        }
      }
      cout << x << "\n";
    }
  }
}
