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 ld = long double;
using pii = pair<int, int>;
const int N = 5e5 + 5, M = 1000000007, INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
void Main();
void debug() { cerr << endl; }
template <typename T, typename... Ts>
void debug(T x, Ts... y) {
  cerr << "\033[31m" << x << "\033[0m";
  if (sizeof...(y) > 0) cerr << ' ';
  debug(y...);
}
template <typename T>
void debug(const T& a, int l, int r, char c) {
  for (int i = l; i <= r; ++i)
    cerr << "\033[31m" << a[i] << "\033[0m" << (i == r ? '\n' : c);
}
template <typename T>
void debug(vector<T> a) {
  for (int i = 0; i < (int)a.size(); ++i)
    cout << "\033[31m" << a[i] << "\033[0m"
         << " \n"[i == (int)a.size() - 1];
}
void print() { cout << '\n'; }
template <typename T, typename... Ts>
void print(T x, Ts... y) {
  cout << x;
  if (sizeof...(y) > 0) cout << ' ';
  print(y...);
}
template <typename T>
void print(const T& a, int l, int r, char c) {
  for (int i = l; i <= r; ++i) cout << a[i] << (i == r ? '\n' : c);
}
template <typename T>
void print(vector<T> a) {
  for (int i = 0; i < (int)a.size(); ++i)
    cout << a[i] << " \n"[i == (int)a.size() - 1];
}
void input() {}
template <typename T, typename... Ts>
void input(T& x, Ts&... y) {
  cin >> x;
  input(y...);
}
template <typename T>
void input(T* a, int l, int r) {
  for (int i = l; i <= r; ++i) cin >> a[i];
}
template <typename T>
void input(vector<T>& a, int l, int r) {
  for (int i = l; i <= r; ++i) cin >> a[i];
}
template <typename T>
void input(vector<T> a) {
  for (auto&& x : a) input(a);
}
template <typename T>
void Max(T& a, T b) {
  if (a < b) a = b;
}
template <typename T>
void Min(T& a, T b) {
  if (a > b) a = b;
}
template <typename T>
void Add(T& a, T b) {
  a += b;
  if (a > M) a -= M;
  if (a < 0) a += M;
}
template <typename T>
void Mul(T& a, T b) {
  a = a * b % M;
}
template <typename T>
T Mod(T a) {
  return (a % M + M) % M;
}
ll qpow(ll a, ll b) {
  ll ret = 1;
  while (b) {
    if (b & 1) ret = ret * a;
    a = a * a, b >>= 1;
  }
  return ret;
}
ll pinv(ll x, ll mod = M) { return qpow(x, mod - 2); }
template <typename... Args>
string sformat(const string& format, Args... args) {
  size_t size = snprintf(nullptr, 0, format.c_str(), args...) + 1;
  unique_ptr<char[]> buf(new char[size]);
  snprintf(buf.get(), size, format.c_str(), args...);
  return string(buf.get(), buf.get() + size - 1);
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  Main();
}
void Main() {
  int T;
  input(T);
  while (T--) {
    ll p, q;
    input(p, q);
    if (q > p) {
      print(p);
      continue;
    }
    if (p % q == 0) {
      int maxn = sqrt(q) + 1;
      vector<pii> factor;
      for (int i = 2; i <= maxn; ++i)
        if (q % i == 0) {
          factor.push_back({i, 0});
          while (q % i == 0) {
            q /= i;
            ++factor.back().second;
          }
        }
      if (q > 1) factor.push_back({q, 1});
      ll minn = LNF;
      for (auto [x, num] : factor) {
        int cnt = 0;
        ll tmp = p;
        while (tmp % x == 0) {
          tmp /= x;
          ++cnt;
        }
        Min(minn, qpow(x, cnt - num + 1));
      }
      print(p / minn);
    } else {
      print(p);
    }
  }
}
