#include <bits/stdc++.h>
using namespace std;
long long n;
int m;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%d", &n, &m);
    if (n % m != 0) {
      printf("%lld\n", n);
      continue;
    }
    int lim = ceil(sqrt(m));
    long long ans = 0;
    long long tmp = m;
    for (int i = 2; i <= lim; i++)
      if (tmp % i == 0) {
        int cnt = 0, cnt2 = 0;
        while (tmp % i == 0) cnt++, tmp /= i;
        long long tmp2 = n;
        while (tmp2 % i == 0) cnt2++, tmp2 /= i;
        long long tmp3 = n;
        while (cnt2 >= cnt) tmp3 /= i, cnt2--;
        ans = max(ans, tmp3);
      }
    if (tmp != 1) {
      while (n % tmp == 0) n /= tmp;
      ans = max(ans, n);
    }
    printf("%lld\n", ans);
  }
  return 0;
}
