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