Oleg's favorite subjects are History and Math, and his favorite branch of mathematics is division.

To improve his division skills, Oleg came up with t pairs of integers p_i and q_i and for each pair decided to find the greatest integer x_i, such that: 

  * p_i is divisible by x_i; 
  * x_i is not divisible by q_i. 

Oleg is really good at division and managed to find all the answers quickly, how about you?

Input

The first line contains an integer t (1 ≤ t ≤ 50) — the number of pairs.

Each of the following t lines contains two integers p_i and q_i (1 ≤ p_i ≤ 10^{18}; 2 ≤ q_i ≤ 10^{9}) — the i-th pair of integers.

Output

Print t integers: the i-th integer is the largest x_i such that p_i is divisible by x_i, but x_i is not divisible by q_i.

One can show that there is always at least one value of x_i satisfying the divisibility conditions for the given constraints.

Example

Input


3
10 4
12 6
179 822


Output


10
4
179

Note

For the first pair, where p_1 = 10 and q_1 = 4, the answer is x_1 = 10, since it is the greatest divisor of 10 and 10 is not divisible by 4.

For the second pair, where p_2 = 12 and q_2 = 6, note that 

  * 12 is not a valid x_2, since 12 is divisible by q_2 = 6; 
  * 6 is not valid x_2 as well: 6 is also divisible by q_2 = 6. 

The next available divisor of p_2 = 12 is 4, which is the answer, since 4 is not divisible by 6.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;
template <class S, class T>
istream &operator>>(istream &is, pair<S, T> &p) {
  return is >> p.first >> p.second;
}
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p) {
  return os << '{' << p.first << "," << p.second << '}';
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &t : v) {
    is >> t;
  }
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '[';
  for (int i = 0; i < int(v.size()); ++i)
    os << v[i] << (i == int(v.size() - 1) ? "" : ",");
  return os << ']';
}
void Yes(bool b) { cout << (b ? "Yes" : "No") << '\n'; }
void YES(bool b) { cout << (b ? "YES" : "NO") << '\n'; }
template <class T>
bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template <typename T>
class prime {
  T n;

 public:
  prime(T n) : n(n) {}
  map<int, int> factorlist() {
    if (n == 1) return {};
    T nn = n;
    map<int, int> ret;
    for (int i = 2; (ll)i * i <= n; i++) {
      if (nn % i != 0) continue;
      int cnt = 0;
      while (nn % i == 0) {
        cnt++;
        nn /= i;
      }
      ret[i] = cnt;
    }
    if (nn != 1) ret[nn]++;
    return ret;
  }
  vector<int> unique_factor() {
    map<int, int> m = factorlist();
    vector<int> ret;
    for (P p : m) ret.push_back(p.first);
    return ret;
  };
  bool isPrime() {
    auto v = factorlist();
    return v.size() == 1 && v[0].second == 1;
  }
  int count_divisor() {
    int ret = 1;
    map<int, int> fl = factorlist(n);
    for (auto p : fl) ret *= p.second + 1;
    return ret;
  };
  vector<T> enum_divisors() {
    vector<T> res;
    for (T i = 1; i * i <= n; i++) {
      if (n % i == 0) {
        res.push_back(i);
        if (n / i != i) res.push_back(n / i);
      }
    }
    sort(res.begin(), res.end());
    return res;
  }
};
void solve() {
  ll p, q;
  cin >> p >> q;
  if (p % q != 0) {
    cout << p << '\n';
    return;
  }
  auto ls = prime<int>(q).factorlist();
  auto cnt = [&](int i) {
    int res = 0;
    ll np = p;
    while (np % i == 0) {
      np /= i;
      res++;
    }
    return res;
  };
  auto pow = [](int i, int j) {
    ll res = 1;
    for (int _ = 0; _ < int(j); ++_) res *= i;
    return res;
  };
  ll mn = linf;
  for (auto [f, s] : ls) {
    int c = cnt(f);
    assert(c >= s);
    chmin(mn, pow(f, c - s + 1));
  }
  cout << p / mn << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  for (int i = 0; i < int(t); ++i) solve();
}
