#include <bits/stdc++.h>
using namespace std;
int ROW[] = {+0, +0, -1, +1};
int COL[] = {+1, -1, +0, +0};
int X[] = {+0, +0, +1, -1, -1, +1, -1, +1};
int Y[] = {-1, +1, +0, +0, +1, +1, -1, -1};
int KX[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int KY[] = {-1, 1, -2, 2, -2, 2, -1, 1};
long long calc(long long num, long long val, long long cnt1, long long cnt2) {
  while (cnt1 >= cnt2) {
    num /= val;
    cnt1--;
  }
  return num;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    long long p, q, n, m;
    scanf("%lld %lld", &p, &q);
    n = p;
    m = q;
    if (p % q) {
      printf("%lld\n", p);
      continue;
    }
    map<long long, long long> mp, mpp;
    for (long long i = 2; i * i <= q; i++) {
      if (q % i) continue;
      while (q % i == 0) {
        mp[i]++;
        q /= i;
      }
    }
    if (q > 1) mp[q]++;
    long long ans = 1LL;
    for (auto it : mp) {
      while (p % it.first == 0) {
        p /= it.first;
        mpp[it.first]++;
      }
      ans = max(ans, calc(n, it.first, mpp[it.first], it.second));
    }
    printf("%lld\n", ans);
  }
  return 0;
}
