#include <bits/stdc++.h>
using namespace std;
class Myfirst {
 private:
  string *name;
  long long int *age;

 public:
  long long int gcd(long long int a, long long int b) {
    if (b == 0) return a;
    a %= b;
    return gcd(b, a);
  }
  long long int exte_gcd(long long int a, long long int b, long long int &x,
                         long long int &y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    long long int x1, y1;
    long long int d = exte_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
  }
  long long int powe(long long int d, long long int s) {
    if (s == 1)
      return d;
    else if (s == 0)
      return 1;
    else {
      long long int u, v = d;
      for (u = 1; u < s; u++) d = d * v;
      return d;
    }
  }
  long long int count_divisors(long long int b) {
    long long int i, count = 0, n = 1;
    for (i = 2; i * i <= b; i++) {
      count = 0;
      if (b % i == 0) {
        while (b % i == 0) {
          b = b / i;
          count++;
        }
        n = n * (count + 1);
      }
    }
    if (b > 1) n = 2 * n;
    return n;
  }
  long long int bigmod(long long int a, long long int b, long long int mod) {
    if (b == 0) return 1;
    long long int x = bigmod(a, b / 2, mod);
    x = (x * x) % mod;
    if (b % 2) x = (x * a) % mod;
    return x;
  }
  long long int phi(long long int n) {
    double result = n;
    for (long long int p = 2; p * p <= n; ++p) {
      if (n % p == 0) {
        while (n % p == 0) n /= p;
        result *= (1.0 - (1.0 / (double)p));
      }
    }
    if (n > 1) result *= (1.0 - (1.0 / (double)n));
    return (long long int)result;
  }
  void solve() {
    long long int t;
    cin >> t;
    while (t--) {
      long long int n, r, i, q = 0, mx = 1, tt = 1;
      cin >> n >> r;
      if (n % r != 0)
        cout << n << endl;
      else {
        for (i = 1; i * i <= r; i++) {
          if (r % i == 0 && i != 1) {
            tt = n;
            while (tt % r == 0) tt = tt / i;
          }
          mx = max(mx, tt);
          if (r % i == 0) {
            tt = n;
            while (tt % (r / i) == 0) tt = tt / (r / i);
          }
          mx = max(mx, tt);
        }
        cout << mx << endl;
      }
    }
  }
};
int main() {
  Myfirst *prg = new Myfirst();
  prg->solve();
}
