#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long mod = 1000000007;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long p, q;
    cin >> p >> q;
    std::vector<long long> factors;
    long long r = p;
    while (r % q == 0) {
      r /= q;
    }
    long long Q = q;
    long long i = 2;
    while (q > 1 and i * i <= Q) {
      if (q % i == 0) {
        factors.push_back(i);
        while (q % i == 0) {
          q /= i;
        }
      }
      i++;
    }
    if (q != 1) {
      factors.push_back(q);
    }
    std::vector<long long> v;
    for (auto it : factors) {
      long long P = p;
      while (P % Q == 0) {
        P /= it;
      }
      v.push_back(P);
    }
    std::cout << *max_element(v.begin(), v.end()) << '\n';
  }
  return 0;
}
