#include <bits/stdc++.h>
const int INF = 1e9 + 5;
using namespace std;
bool prime[100010];
vector<long long> primes;
void genPrimes(int n) {
  memset(prime, 1, sizeof(prime));
  for (int i = 2; i * i < n; i++) {
    if (prime[i]) {
      for (int j = i * i; j < n; j += i) {
        prime[j] = 0;
      }
    }
  }
  for (long long i = 2; i < n; i++) {
    if (prime[i]) {
      primes.push_back(i);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  genPrimes(100000);
  int t;
  cin >> t;
  while (t--) {
    long long p, q;
    cin >> p >> q;
    if (p % q != 0)
      cout << p << endl;
    else {
      map<long long, long long> factQ;
      long long b = q;
      int now = 0;
      while (b != 1) {
        if (now == (int)primes.size()) {
          factQ[b] = 1;
          break;
        }
        if (b % primes[now] == 0) {
          factQ[primes[now]]++;
          b /= primes[now];
        } else {
          now++;
        }
      }
      long long res = 1;
      for (auto it = factQ.begin(); it != factQ.end(); it++) {
        pair<long long, long long> here = *it;
        long long a = p;
        while (a % q == 0) {
          a /= here.first;
        }
        res = max(res, a);
      }
      cout << res << endl;
    }
  }
  return 0;
}
