#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
long long a, b, c, d, ans, t;
int main() {
  cin >> t;
  while (t--) {
    ans = 0;
    cin >> a >> b;
    if (a % b == 0)
      for (int i = 2; i * i <= b; i++) {
        if (b % i == 0) {
          d = b / i, c = a;
          while (c % b == 0) c /= i;
          ans = max(ans, c), c = a;
          while (c % b == 0) c /= d;
          ans = max(ans, c);
        }
      }
    else
      ans = a;
    while (a % b == 0) a /= b;
    ans = max(a, ans);
    cout << ans << endl;
  }
}
