#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e7 + 10;
bool notprime[maxn];
int prime[maxn];
int cnt;
void getprime() {
  notprime[0] = notprime[1] = 1;
  cnt = 0;
  for (int i = 2; i < maxn; ++i) {
    if (!notprime[i]) {
      prime[cnt++] = i;
    }
    for (int j = 0; j < cnt && 1ll * i * prime[j] < maxn; ++j) {
      notprime[i * prime[j]] = 1;
    }
  }
}
long long p, q;
long long solve(long long a, int b) {
  long long res = 1;
  for (int i = 1; i <= b; i++) {
    res *= a;
  }
  return res;
}
long long quick(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> p >> q;
    if (p % q != 0) {
      cout << p << endl;
      continue;
    }
    long long tmp = p;
    long long ans = 1e18;
    for (long long i = 2; i * i <= q; i++) {
      if (q % i == 0) {
        int num1 = 0, num2 = 0;
        while (q % i == 0) {
          q /= i;
          num1++;
        }
        while (p % i == 0) {
          p /= i;
          num2++;
        }
        ans = min(ans, quick(i, num2 - num1 + 1));
      }
    }
    if (q != 1) {
      int num = 0;
      while (p % q == 0) {
        p /= q;
        num++;
      }
      ans = min(ans, quick(q, num));
    }
    cout << tmp / ans << endl;
  }
}
