#include <bits/stdc++.h>
using namespace std;
const long long Maxn = 50;
long long t;
long long ksm(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a;
    a = a * a;
    b >>= 1;
  }
  return ans;
}
signed main() {
  scanf("%lld", &t);
  while (t--) {
    long long p, q;
    scanf("%lld%lld", &p, &q);
    map<long long, long long> cntq;
    long long x = p, y = q, ans = 0;
    for (register long long i = 2; i <= y / i; i++)
      if (y % i == 0) {
        long long t = 0, t1 = 0;
        while (y % i == 0) y /= i, ++t1;
        while (x % i == 0) x /= i, ++t;
        if (t < t1) {
          ans = p;
          break;
        }
        ans = max(ans, p / ksm(i, t - t1 + 1));
      }
    if (y != 1) {
      long long t = 0;
      while (x % y == 0) x /= y, ++t;
      if (t >= 1) {
        ans = max(ans, p / ksm(y, t));
      } else
        ans = p;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
