#include <bits/stdc++.h>
long long p, q, mult[1000005], fac[1000005], ans;
int cnt;
int main(void) {
  int t;
  for (scanf("%d", &t); t--;) {
    scanf("%lld %lld", &p, &q);
    cnt = 0;
    ans = 0;
    if (p % q) {
      printf("%lld\n", p);
      continue;
    }
    for (long long i = 2; i * i <= q; ++i)
      if (q % i == 0) {
        mult[++cnt] = 1;
        fac[cnt] = i;
        while (q % i == 0) {
          mult[cnt] *= i;
          q /= i;
        }
      }
    if (q > 1) mult[cnt] = fac[++cnt] = q;
    for (int i = 1; i <= cnt; ++i) {
      long long remain = p;
      while (remain % fac[i] == 0) remain /= fac[i];
      remain *= mult[i] / fac[i];
      ans = remain > ans ? remain : ans;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
