#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    long long p, q;
    cin >> p >> q;
    if (p % q != 0)
      cout << p << endl;
    else {
      long long x = q;
      long long ans = 1;
      for (long long i = 2; i <= (long long)sqrt(x); i++) {
        if (x % i == 0) {
          while (x % i == 0) x /= i;
          long long tp = p;
          while (tp % q == 0) tp /= i;
          ans = max(ans, tp);
        }
      }
      if (x > 1) {
        long long tp = p;
        while (tp % q == 0) tp /= x;
        ans = max(ans, tp);
      }
      cout << ans << endl;
    }
  }
}
