#include <bits/stdc++.h>
using namespace std;
long long p, q, ans;
long long solve(long long x) {
  if (x == 1) return x;
  long long k = p;
  while (k % q == 0) k /= x;
  return k;
}
void fun(long long x) {
  for (long long i = 1; i <= x / i; i++) {
    if (x % i == 0) {
      long long a = i, b = x / i;
      ans = max(ans, solve(a));
      ans = max(ans, solve(b));
    }
  }
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    ans = 0;
    scanf("%lld%lld", &p, &q);
    fun(q);
    if (ans)
      printf("%lld\n", ans);
    else
      printf("1\n");
  }
  return 0;
}
