#include <bits/stdc++.h>
using namespace std;
long long T, a, b;
long long Div(long long x) {
  if (x == 1) return 1;
  long long t = a;
  while (t % b == 0) t /= x;
  return t;
}
int main() {
  cin >> T;
  while (T--) {
    cin >> a >> b;
    if (a % b == 0) {
      long long ans = 1;
      for (long long i = 1; i <= sqrt(b); i++) {
        if (b % i) continue;
        ans = max(ans, Div(i));
        ans = max(ans, Div(b / i));
      }
      cout << ans << endl;
    } else {
      cout << a << endl;
    }
  }
  return 0;
}
