#include <bits/stdc++.h>
using namespace std;
long long ar[100001];
long long dp[2001][2001];
void add_self(long long &a, long long b) {
  a += b;
  if (a > 1000000007) a -= 1000000007;
}
int powb(int x, int y) {
  int res = 1;
  x = x % 1000000007;
  while (y > 0) {
    if (y % 2) res = (res * x) % 1000000007;
    y /= 2;
    x = (x * x) % 1000000007;
  }
  return res;
}
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <typename T>
void i_vector(vector<T> &a) {
  for (int i = 0; i < a.size(); i++) cin >> a[i];
}
void solve() {
  long long p, q;
  cin >> p >> q;
  long long x = 0;
  if (p < q || p % q)
    x = p;
  else {
    long long k = q;
    set<long long> st;
    while (q % 2 == 0) {
      st.insert(2);
      q /= 2;
    }
    for (int i = 3; i <= sqrt(q); i = i + 2) {
      while (q % i == 0) {
        st.insert(i);
        q /= i;
      }
    }
    if (q > 2) st.insert(q);
    for (auto it : st) {
      long long h = p;
      while (h % k == 0) {
        h /= it;
      }
      x = max(h, x);
    }
  }
  cout << x << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;
  int t = 0;
  cin >> t;
  while (t--) solve();
}
