#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long s = 0, t = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') t = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * t;
}
int main() {
  int t = read();
  while (t--) {
    long long p = read(), q = read();
    if (p % q == 0) {
      long long ans = 0;
      for (int i = 1; i * i <= q; i++) {
        if (q % i == 0) {
          long long wei;
          if (i != 1) {
            wei = p;
            while (wei % q == 0) wei /= i;
            ans = max(ans, wei);
          }
          int j = q / i;
          wei = p;
          while (wei % q == 0) wei /= j;
          ans = max(ans, wei);
        }
      }
      printf("%lld\n", ans);
    } else
      printf("%lld\n", p);
  }
  return 0;
}
