#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0, f = 1;
  while ((c < '0' || c > '9') && c ^ '-') c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - 48;
    c = getchar();
  }
  return x * f;
}
const int N = 5e4 + 10;
int prime[N / 5], cnt = 0;
bool check[N];
int t, dl, dui[N / 5], top = 0, ci2[N / 5], ci[N / 5];
long long n, dan = 0;
int m;
int main() {
  check[1] = 1;
  for (int i = 2; i <= N - 10; i++) {
    if (!check[i]) prime[++cnt] = i;
    for (int j = 1; j <= cnt && i * prime[j] <= N - 10; j++) {
      check[i * prime[j]] = 1;
      if (!(i % prime[j])) break;
    }
  }
  t = read();
  while (t--) {
    top = 0;
    dan = 0;
    dl = 0;
    n = read();
    m = read();
    if (n % m) {
      cout << n << "\n";
      continue;
    }
    long long jin = n;
    int jim = m;
    for (int i = 1; i <= cnt; i++) {
      ci[i] = 0;
      while (!(m % prime[i])) ci[i]++, m /= prime[i];
    }
    if (m > 1) dl = m;
    for (int i = 1; i <= cnt; i++)
      if (ci[i]) {
        n = jin;
        while (!(n % jim)) n /= prime[i];
        if (n > dan) dan = n;
      }
    if (dl) {
      n = jin;
      while (!(n % jim)) n /= dl;
      if (n > dan) dan = n;
    }
    cout << dan << "\n";
  }
  return 0;
}
