#include <bits/stdc++.h>
using namespace std;
bool prime[9000000];
vector<long long int> v;
void sieve() {
  prime[0] = true;
  prime[1] = true;
  for (long long i = 2; i < 9000000; i++) {
    if (prime[i] == false) {
      v.push_back(i);
      for (long long j = i * i; j < 9000000; j += i) prime[j] = true;
    }
  }
}
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long dp[4001][4001];
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  sieve();
  cin >> t;
  while (t--) {
    long long p, q;
    cin >> p >> q;
    long long ans = 1;
    if (p % q != 0)
      cout << p << '\n';
    else {
      ans = 1;
      long long x = q;
      for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) {
          long long t = p;
          while (t % q == 0) t /= i;
          ans = max(ans, t);
        }
        while (x % i == 0) x /= i;
      }
      if (x > 1) {
        long long t = p;
        while (t % q == 0) t /= x;
        ans = max(ans, t);
      }
      cout << ans << '\n';
    }
  }
  return 0;
}
