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>
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
bool __hack = std::ios::sync_with_stdio(false);
auto __hack1 = cin.tie(nullptr);
struct Input {
  Input(istream &in) : in(&in) {}
  template <class T>
  T next() const {
    T x;
    *in >> x;
    return x;
  }
  int ni() const { return next<int>(); }
  int64_t ni64() const { return next<int64_t>(); }
  istream *in;
};
Input in(cin);
class Output {
 private:
  ostream *out;
  template <typename T>
  void printSingle(const T &value) {
    *out << value;
  }

 public:
  Output(ostream &out) : out(&out) {}
  inline void print() {}
  template <typename T, typename... Ts>
  inline void print(const T &f, const Ts &...args) {
    printSingle(f);
    if (sizeof...(args) != 0) {
      *out << ' ';
      print(args...);
    }
  }
  template <typename... Ts>
  inline void println(const Ts &...args) {
    print(args...);
    (*out) << '\n';
  }
  template <typename... Ts>
  inline void operator()(const Ts &...args) {
    println(args...);
  }
};
Output out(cout);
namespace template_util {
constexpr int bytecount(uint64_t x) { return x ? 1 + bytecount(x >> 8) : 0; }
template <int N>
struct bytetype {};
template <uint64_t N>
struct minimal_uint : bytetype<bytecount(N)> {};
}  // namespace template_util
template <class T>
bool isPrime(T x) {
  if (x == 1) {
    return false;
  }
  if (x == 2) {
    return true;
  }
  if (x % 2 == 0) {
    return false;
  }
  for (T i = 3; i * i <= x; i += 2) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
}
vector<pair<int64_t, int>> factorize(int64_t number) {
  vector<pair<int64_t, int>> res;
  if (number % 2 == 0) {
    int power = 0;
    do {
      power++;
      number /= 2;
    } while (number % 2 == 0);
    res.push_back({2, power});
  }
  for (int64_t i = 3; i * i <= number; i += 2) {
    if (number % i == 0) {
      int power = 0;
      do {
        power++;
        number /= i;
      } while (number % i == 0);
      res.push_back({i, power});
    }
  }
  if (number != 1) {
    res.push_back({number, 1});
  }
  return res;
}
void solveOne() {
  auto p = in.ni64();
  auto q = in.ni64();
  if (p % q != 0) {
    out(p);
    return;
  }
  if (isPrime(q)) {
    while (p % q == 0) {
      p /= q;
    }
    out(p);
    return;
  }
  auto qFactor = factorize(q);
  int64_t res = 1;
  for (const auto &f : qFactor) {
    auto P = p;
    while (P % f.first == 0) {
      P /= f.first;
    }
    for (int j = 0; j < (f.second - 1); ++j) {
      P *= f.first;
    }
    res = max(res, P);
  }
  out(res);
}
void solve(istream &inStream, ostream &outStream) {
  in = Input(inStream);
  out = Output(outStream);
  auto tests = in.ni();
  while (tests--) {
    solveOne();
  }
}
int main() {
  solve(cin, cout);
  return 0;
}
