#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int mod = 1e9 + 7;
long long a[105];
long long b[105];
bool cmp(long long x, long long y) { return x > y; }
int main() {
  long long t;
  scanf("%lld", &t);
  while (t--) {
    long long p, q;
    scanf("%lld", &p);
    scanf("%lld", &q);
    long long pt = p;
    long long qt = q;
    long long ans = -1;
    for (int i = 2; i * i <= qt; i++) {
      if (qt % i == 0) {
        while (qt % i == 0) qt /= i;
        long long temp = p;
        while (temp % q == 0 && temp % i == 0) temp /= i;
        ans = max(ans, temp);
      }
    }
    if (qt > 1) {
      long long temp = p;
      while (temp % q == 0 && temp % qt == 0) temp /= qt;
      ans = max(ans, temp);
    }
    printf("%lld\n", ans);
    ;
  }
}
