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;
bool is_Smaller_str(string str1, string str2) {
  long long n1 = str1.length(), n2 = str2.length();
  if (n1 < n2) return true;
  if (n2 < n1) return false;
  for (long long i = 0; i < n1; i++)
    if (str1[i] < str2[i])
      return true;
    else if (str1[i] > str2[i])
      return false;
  return false;
}
class Graph {
  long long V;
  list<long long>* adj;
  void DFSUtil(long long v, bool visited[]);

 public:
  Graph(long long V);
  void addEdge(long long v, long long w);
  long long NumberOfconnectedComponents();
};
long long Graph::NumberOfconnectedComponents() {
  bool* visited = new bool[V];
  long long count = 0;
  for (long long v = 0; v < V; v++) visited[v] = false;
  for (long long v = 0; v < V; v++) {
    if (visited[v] == false) {
      DFSUtil(v, visited);
      count += 1;
    }
  }
  return count;
}
void Graph::DFSUtil(long long v, bool visited[]) {
  visited[v] = true;
  list<long long>::iterator i;
  for (i = adj[v].begin(); i != adj[v].end(); ++i)
    if (!visited[*i]) DFSUtil(*i, visited);
}
Graph::Graph(long long V) {
  this->V = V;
  adj = new list<long long>[V];
}
void Graph::addEdge(long long v, long long w) {
  adj[v].push_back(w);
  adj[w].push_back(v);
}
string find_Diff_str(string str1, string str2) {
  if (is_Smaller_str(str1, str2)) swap(str1, str2);
  string str = "";
  long long n1 = str1.length(), n2 = str2.length();
  reverse(str1.begin(), str1.end());
  reverse(str2.begin(), str2.end());
  long long carry = 0;
  for (long long i = 0; i < n2; i++) {
    long long sub = ((str1[i] - '0') - (str2[i] - '0') - carry);
    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else
      carry = 0;
    str.push_back(sub + '0');
  }
  for (long long i = n2; i < n1; i++) {
    long long sub = ((str1[i] - '0') - carry);
    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else
      carry = 0;
    str.push_back(sub + '0');
  }
  reverse(str.begin(), str.end());
  return str;
}
string find_sum_str(string str1, string str2) {
  if (str1.length() > str2.length()) swap(str1, str2);
  string str = "";
  long long n1 = str1.length(), n2 = str2.length();
  reverse(str1.begin(), str1.end());
  reverse(str2.begin(), str2.end());
  long long carry = 0;
  for (long long i = 0; i < n1; i++) {
    long long sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
    str.push_back(sum % 10 + '0');
    carry = sum / 10;
  }
  for (long long i = n1; i < n2; i++) {
    long long sum = ((str2[i] - '0') + carry);
    str.push_back(sum % 10 + '0');
    carry = sum / 10;
  }
  if (carry) str.push_back(carry + '0');
  reverse(str.begin(), str.end());
  return str;
}
void FAST() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
long long Rselect(vector<long long> v, long long i, long long l, long long r);
long long partition(vector<long long> v, long long l, long long r);
void scanc(vector<char>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    char num;
    cin >> num;
    v.push_back(num);
  }
}
void scanP(vector<pair<long long, long long> >& v, long long n) {
  for (long long i = 0; i < n; i++) {
    long long num1, num2;
    cin >> num1 >> num2;
    pair<long long, long long> p = {num1, num2};
    v.push_back(p);
  }
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& vec) {
  for (auto& i : vec) {
    stream << i << ' ';
  }
  stream << '\n';
  return stream;
}
template <class T>
istream& operator>>(istream& stream, vector<T>& vec) {
  for (auto& i : vec) {
    stream >> i;
  }
  return stream;
}
void solve();
void scanN(vector<long long>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    long long num;
    cin >> num;
    v.push_back(num);
  }
}
void scans(vector<string>& v, long long n) {
  for (long long i = 0; i < n; i++) {
    string s;
    cin >> s;
    v.push_back(s);
  }
}
long long modfactorial(long long n, long long p) {
  if (n >= p) return 0;
  long long result = 1;
  for (long long i = 1; i < n + 1; i++) {
    result = result * i;
    result = result % p;
  }
  return result;
}
long long MI(long long a, long long b, long long s0 = 1, long long s1 = 0) {
  long long k = b;
  if (b == 0)
    return s0;
  else {
    return MI(b, a % b, s1, s0 - s1 * (a / b));
  }
}
long long choose(long long a, long long b, long long c = 1000000007) {
  if (a < b) return 0;
  long long x = modfactorial(a, c);
  long long y = modfactorial(b, c);
  long long z = modfactorial(a - b, c);
  long long y_ = MI(y, c, 1, 0);
  if (y_ < 0) y_ = y_ + c;
  long long z_ = MI(z, c, 1, 0);
  if (z_ < 0) z_ = z_ + c;
  long long mul = (x * y_) % c;
  mul = (mul * z_) % c;
  return mul;
}
void SOLT() {
  long long test;
  cin >> test;
  while (test--) {
    solve();
  }
}
long long modpow(long long n, long long p, long long k) {
  n = n % k;
  long long res = 1;
  while (p > 0) {
    if (p % 2 == 1) res = res * n % k;
    n = n * n % k;
    p = p / 2;
  }
  return res;
}
long long __pow(long long n, long long p) {
  long long res = 1;
  while (p > 0) {
    if (p % 2 == 1) res = res * n;
    n = n * n;
    p = p / 2;
  }
  return res;
}
long long str_mod_num(string b, long long c) {
  long long k = b.size();
  vector<long long> mod(k + 1);
  mod[0] = 1;
  for (long long i = 1; i < k + 1; i++) {
    mod[i] = 10 * mod[i - 1];
    mod[i] %= c;
  }
  long long rem = 0;
  for (long long i = k - 1; i > -1; i--) {
    long long num = b[i] - '0';
    num *= mod[k - 1 - i];
    num %= c;
    rem += num;
    rem %= c;
  }
  return rem;
}
long long str_pow_str_mod_num(string b, string n, long long c) {
  long long tr = n.size();
  long long rem = str_mod_num(b, c);
  long long time_pass = n[0] - '0';
  long long ans = modpow(rem, time_pass, c);
  for (long long i = 1; i < tr; i++) {
    time_pass = n[i] - '0';
    ans = modpow(ans, 10, c);
    ans *= modpow(rem, time_pass, c);
    ans %= c;
  }
  return ans;
}
bool isPrime(long long a) {
  if (a == 1) return 0;
  for (long long i = 2; i * i <= a; ++i)
    if (a % i == 0) return false;
  return true;
}
bool useflushdivisible(long long a) {
  cout << a << endl;
  fflush(stdout);
  char sl[10];
  scanf("%s", sl);
  return sl[0] == 'y' || sl[0] == 'Y';
}
long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) n = n / i;
      result = result - result / i;
    }
  }
  if (n > 1) result = result - result / n;
  return result;
}
bool cmp(pair<long long, long long> x, pair<long long, long long> y) {
  if (x.first == y.first) return x.second < y.second;
  return x.first < y.first;
}
vector<long long> getfactors(long long n) {
  vector<long long> factors;
  for (long long i = 1; i < (long long)sqrt(n) + 1; i++) {
    if (n % i == 0) {
      factors.push_back(i);
      if (i != (n / i)) factors.push_back(n / i);
    }
  }
  return factors;
}
long long Binary_Search(vector<long long>& a, long long low, long long high,
                        long long key) {
  if (high < low) return a[low - 1];
  long long mid = low + (high - low) / 2;
  if (key == a[mid])
    return a[mid];
  else if (key < a[mid])
    return Binary_Search(a, low, mid - 1, key);
  return Binary_Search(a, mid + 1, high, key);
}
double area(long long x1, long long y1, long long x2, long long y2,
            long long x3, long long y3) {
  return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
}
bool isInside(long long x1, long long y1, long long x2, long long y2,
              long long x3, long long y3, long long x, long long y) {
  double A = area(x1, y1, x2, y2, x3, y3);
  double A1 = area(x, y, x2, y2, x3, y3);
  double A2 = area(x1, y1, x, y, x3, y3);
  double A3 = area(x1, y1, x2, y2, x, y);
  return (A == A1 + A2 + A3);
}
long long factorial(long long n) {
  if (n <= 1)
    return 1;
  else
    return n * factorial(n - 1);
}
long long fun(vector<long long> arr, long long n) {
  long long x = arr[0];
  for (long long i = 1; i < n; i++) x = x ^ arr[i];
  return x;
}
long long find_cost(vector<long long> l) {
  long long n = l.size(), ans = 0;
  for (long long i = 0; i < n - 1; i++) {
    long long j = min_element(l.begin() + i, l.end()) - l.begin();
    ans += j - i + 1;
    reverse(l.begin() + i, l.begin() + j + 1);
  }
  return ans;
}
long long tower_of_hanoi_number_of_ways(long long n, long long a = 3) {
  if (n == 1)
    return 1;
  else {
    long long p = tower_of_hanoi_number_of_ways(n - 1, 1);
    long long q = tower_of_hanoi_number_of_ways(n - 1, 2);
    return p + q + 1;
  }
}
void tower_of_hanoi_details(long long n, char a = '1', char b = '2',
                            char c = '3') {
  if (n == 1) {
    cout << a << " " << c << endl;
    return;
  }
  tower_of_hanoi_details(n - 1, a, c, b);
  cout << a << " " << c << endl;
  tower_of_hanoi_details(n - 1, b, a, c);
}
int32_t main() {
  FAST();
  long long test = 1;
  cin >> test;
  for (long long tt = 1; tt <= test; tt++) {
    solve();
  }
  return 0;
}
void solve() {
  long long p, q;
  cin >> p >> q;
  if (p < q) {
    cout << p << endl;
    return;
  } else {
    if (p % q) {
      cout << p << endl;
      return;
    }
    vector<long long> primefacq = getfactors(q);
    long long t = q;
    long long x = -1;
    for (auto v : primefacq) {
      if (isPrime(v)) {
        long long t = p;
        while (t % q == 0) {
          t /= v;
        }
        x = max(x, t);
      }
    }
    cout << x << endl;
  }
}
long long Rselect(vector<long long> v, long long i, long long l, long long r) {
  if (l == r) return v[l];
  long long pivot = partition(v, l, r);
  if (pivot == i)
    return v[pivot - 1];
  else if (pivot < i) {
    return Rselect(v, i, pivot, r);
  } else {
    return Rselect(v, i, l, pivot - 2);
  }
}
long long partition(vector<long long> v, long long l, long long r) {
  long long pivot_index = rand() % (r - l + 1) + l;
  swap(v[pivot_index], v[l]);
  long long i = l + 1, j = l + 1;
  while (j <= r) {
    if (v[j] < v[l]) {
      swap(v[j], v[i]);
      i++;
    }
    j++;
  }
  swap(v[l], v[i - 1]);
  return i;
}
