#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &ret) {
  T x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  ret = x * f;
}
template <class T>
inline T lowbit(T x) {
  return x & (-x);
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
inline T Pow(T a, T b, T p) {
  T ret = 1;
  a %= p;
  for (; b; b >>= 1, a = a * a % p)
    if (b & 1) (ret *= a) %= p;
  return ret;
}
const int N = 1010;
long long p[N], cnt[N];
long long solv(long long P, long long q) {
  long long p_raw = P;
  int tot = 0;
  for (long long i = 2; i * i <= q; i++)
    if (q % i == 0) {
      p[tot] = i;
      cnt[tot] = 0;
      while (q % i == 0) cnt[tot]++, q /= i;
      tot++;
    }
  if (q != 1) p[tot] = q, cnt[tot++] = 1;
  long long res = 1;
  for (long long i = (0); i <= (tot - 1); i++) {
    long long cur = 0, pn = 1;
    while (P % p[i] == 0) {
      cur++, P /= p[i];
      if (cur >= cnt[i]) pn *= p[i];
    }
    if (cur < cnt[i]) return p_raw;
    res = max(p_raw / pn, res);
  }
  return res;
}
int main() {
  int T;
  read(T);
  while (T--) {
    long long p, q;
    read(p);
    read(q);
    printf("%lld\n", solv(p, q));
  }
}
