#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
void solve() {
  long long p, q;
  scanf("%lld", &p);
  scanf("%lld", &q);
  if (p % q != 0) {
    printf("%lld\n", p);
    return;
  }
  long long c = q, c2 = p;
  long long ans = 0;
  for (long long i = 2; i * i <= c; ++i) {
    if (c % i == 0) {
      int f1 = 0;
      while (c % i == 0) f1++, c /= i;
      int f2 = 0;
      long long sol = p;
      while (c2 % i == 0) f2++, c2 /= i, sol /= i;
      for (int t = 1; t < f1; ++t) sol *= i;
      ans = max(ans, sol);
    }
  }
  if (c > 1) {
    long long sol = p;
    while (c2 % c == 0) c2 /= c, sol /= c;
    ans = max(ans, sol);
  }
  printf("%lld\n", ans);
}
int main() {
  long long t;
  scanf("%lld", &t);
  while (t--) solve();
  return 0;
}
