#include <bits/stdc++.h>
using namespace std;
long long p, q;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld", &p, &q);
    long long m = sqrt(q), ans = 1;
    for (int i = 2; i <= m; i++)
      if (q % i == 0) {
        int c = 0, e = 0;
        long long val = p;
        while (q % i == 0) q /= i, c++;
        while (val % i == 0) val /= i, e++;
        if (e < c)
          ans = max(ans, p);
        else {
          for (int j = 0; j < c - 1; j++) val *= i;
          ans = max(ans, val);
        }
      }
    if (q > 1) {
      if (p % q == 0) {
        long long val = p;
        while (val % q == 0) val /= q;
        ans = max(ans, val);
      } else
        ans = max(ans, p);
    }
    printf("%lld\n", ans);
  }
  return 0;
}
