#include <bits/stdc++.h>
using namespace std;
void kehsihba() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
void solve() {
  long long a, b;
  cin >> a >> b;
  if (a % b != 0) {
    cout << a;
    cout << '\n';
    ;
    return;
  }
  set<long long> s;
  for (long long i = 1; i * i <= b; i++) {
    if (b % i == 0) {
      s.insert(i), s.insert(b / i);
    }
  }
  long long ans = -1;
  for (auto lol : s) {
    if (lol == *s.begin()) {
      continue;
    }
    long long x = a / lol;
    while (x % b == 0) {
      x = x / lol;
    }
    ans = max(ans, x);
  }
  cout << ans;
  cout << '\n';
  ;
}
int32_t main() {
  kehsihba();
  long long t = 1;
  cin >> t;
  for (long long k = 1; k <= t; k++) {
    solve();
  }
}
