#include <bits/stdc++.h>
using namespace std;
int T;
long long p, q, ans;
void check(int i) {
  long long now = p;
  while (now % q == 0) now /= i;
  ans = max(ans, now);
}
int main() {
  scanf("%d", &T);
  while (T--) {
    ans = -1;
    scanf("%lld%lld", &p, &q);
    if (p % q) {
      printf("%lld\n", p);
      continue;
    }
    long long tmp = q;
    for (int i = 2; i * i <= tmp; i++) {
      if (q % i == 0) {
        while (tmp % i == 0) tmp /= i;
        check(i);
      }
    }
    if (tmp != 1) check(tmp);
    printf("%lld\n", ans);
  }
  return 0;
}
