#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
using namespace std;
const long long N = 2e5;
const long long M = 998244353;
long long bin_pow(long long a, long long n) {
  if (n == 0) return 1;
  if (n % 2 == 1)
    return a * bin_pow(a, n - 1);
  else {
    long long x = bin_pow(a, n / 2);
    return x * x;
  }
}
long long solve() {
  long long p, q;
  cin >> p >> q;
  if (p % q != 0) return p;
  long long k = p;
  for (long long b = 2; b * b <= q; b++) {
    if (q % b != 0) continue;
    long long gg = 0;
    while (q % b == 0) {
      gg++;
      q /= b;
    }
    long long f = 0;
    long long p1 = p;
    while (p1 % b == 0) {
      f++;
      p1 /= b;
    }
    long long st = f - gg + 1;
    k = min(k, bin_pow(b, st));
  }
  if (q > 1) {
    long long b = q;
    long long gg = 0;
    while (q % b == 0) {
      gg++;
      q /= b;
    }
    long long f = 0;
    long long p1 = p;
    while (p1 % b == 0) {
      f++;
      p1 /= b;
    }
    long long st = f - gg + 1;
    k = min(k, bin_pow(b, st));
  }
  return p / k;
}
int32_t main() {
  long long tt;
  cin >> tt;
  while (tt--) {
    cout << (solve()) << "\n";
  }
}
