#include <bits/stdc++.h>
#pragma GCC optimize("-O2")
using namespace std;
const int LIM = 2e5 + 5, MOD = 1e9 + 7;
const long double EPS = 1e-9;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int tests = 1;
  cin >> tests;
  while (tests--) {
    long long p, q;
    long long op;
    cin >> p >> q;
    op = p;
    long long mi = p;
    for (int i = 2; i < 1e5; ++i) {
      if ((q % i) == 0) {
        long long c = 1;
        long long num = 0;
        while ((q % i) == 0) {
          num++;
          q /= i;
        }
        long long num2 = 0;
        while ((p % i) == 0) {
          num2++;
          p /= i;
        }
        for (int j = 0; j < num2 - num + 1; ++j) {
          c *= i;
        }
        mi = min(mi, c);
      }
    }
    if (q > 1) {
      long long num1 = 1;
      long long num2 = 0;
      while ((p % q) == 0) {
        p /= q;
        num2++;
      }
      long long c = 1;
      for (int j = 0; j < num2 - num1 + 1; ++j) {
        c *= q;
      }
      mi = min(mi, c);
    }
    cout << op / mi << '\n';
  }
  return 0;
}
