#include <bits/stdc++.h>
using namespace std;
unsigned long long t, p, q;
int main() {
  cin >> t;
  while (t--) {
    cin >> p >> q;
    unsigned long long d = 2, answer = 0, b = q;
    while (d * d <= b) {
      if (b % d == 0) {
        unsigned long long a = p;
        while (a % b == 0) a /= d;
        answer = max(answer, a);
      }
      while (b % d == 0) b /= d;
      d++;
    }
    if (b > 1) {
      unsigned long long a = p;
      while (a % q == 0) a /= b;
      answer = max(answer, a);
    }
    cout << answer << "\n";
  }
}
