#include <bits/stdc++.h>
using namespace std;
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v);
template <typename A, typename B>
ostream &operator<<(ostream &cout, pair<A, B> const &p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v) {
  cout << "[";
  for (int i = 0; i < v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
template <typename A, typename B>
istream &operator>>(istream &cin, pair<A, B> &p) {
  cin >> p.first;
  return cin >> p.second;
}
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
void usaco(string filename) {
  freopen((filename + ".in").c_str(), "r", stdin);
  freopen((filename + ".out").c_str(), "w", stdout);
}
const long double pi = 3.14159265358979323846;
namespace number_theory {
bool prime[15000105];
void sieve(int n) {
  for (long long i = 0; i <= n; i++) prime[i] = 1;
  for (long long p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (long long i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
  prime[1] = prime[0] = 0;
}
vector<long long> primelist;
bool __primes_generated__ = 0;
void genprimes(int n) {
  __primes_generated__ = 1;
  sieve(n + 1);
  for (long long i = 2; i <= n; i++)
    if (prime[i]) primelist.push_back(i);
}
vector<long long> factors(long long n) {
  if (!__primes_generated__) {
    cerr << "Call genprimes you dope" << endl;
    exit(1);
  }
  vector<long long> facs;
  for (long long i = 0;
       primelist[i] * primelist[i] <= n && i < primelist.size(); i++) {
    if (n % primelist[i] == 0) {
      while (n % primelist[i] == 0) {
        n /= primelist[i];
        facs.push_back(primelist[i]);
      }
    }
  }
  if (n > 1) {
    facs.push_back(n);
  }
  return facs;
}
}  // namespace number_theory
using namespace number_theory;
long long n, m, k, q, l, r, x, y, z;
const long long template_array_size = 1e6 + 3862;
long long a[template_array_size];
long long b[template_array_size];
long long c[template_array_size];
string second, t;
long long ans = 0;
void solve(int tc = 0) {
  long long p, q;
  cin >> p >> q;
  if (p % q != 0) {
    cout << p << '\n';
    return;
  }
  vector<long long> facs = factors(q);
  map<long long, long long> cnt;
  for (long long x : facs) ++cnt[x];
  long long ans = p;
  for (pair<long long, long long> x : cnt) {
    long long pow_p = 0;
    long long op = p;
    while (op % x.first == 0) {
      op /= x.first;
      ++pow_p;
    }
    long long diff = pow_p - x.second + 1;
    long long div = 1;
    for (long long i = 0; i < diff; i++) div *= x.first;
    ans = min(ans, div);
  }
  cout << p / ans << '\n';
}
int main() {
  { ios_base::sync_with_stdio(false); }
  { cin.tie(NULL); }
  genprimes(1e6);
  int tc = 1;
  cin >> tc;
  for (int t = 0; t < tc; t++) solve(t);
}
