#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long x;
  cin >> x;
  while (x--) {
    long long p, q;
    cin >> p >> q;
    if (q > p) {
      cout << p << endl;
    } else if (p >= q) {
      if (p % q != 0) {
        cout << p << endl;
      } else {
        map<long long, long long> primes;
        long long n = q;
        for (long long i = 2; i * i <= n; i++) {
          if (n % i == 0) {
            while (n % i == 0 && n != 1) {
              n /= i;
              primes[i]++;
            }
          }
        }
        if (n > 1) {
          primes[n]++;
        }
        long long ans = -1;
        for (auto it : primes) {
          long long num = p;
          long long prime = it.first;
          while (num % prime == 0) {
            if (num % q != 0) {
              break;
            }
            num /= prime;
          }
          ans = max(ans, num);
        }
        cout << ans << endl;
      }
    }
  }
  return 0;
}
