#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int d4i[4] = {-1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
string to_string(char c) { return string(1, c); }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(vector<bool> v) {
  string res;
  for (int i = (0); i < ((int)(v).size()); ++i) res += char('0' + v[i]);
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res;
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return 31 - __builtin_clz(x); }
const long long MOD = 1e9 + 7;
const int MX = 1e5 + 5;
int tree[1];
int sum(int k) {
  int a = 0;
  while (k >= 1) {
    a += tree[k];
    k -= k & -k;
  }
  return a;
}
void add(int k, int x) {
  while (k <= MX) {
    tree[k] += x;
    k += k & -k;
  }
}
vector<int> adj[MX];
int depth[MX];
int diam;
int dfs(int u, int p) {
  int len = 0;
  for (int& v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      int cur = 1 + dfs(v, u);
      ckmax(diam, cur + len);
      ckmax(len, cur);
    }
  return len;
}
int dp[205][205][205] = {0};
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = (0); i < (n); ++i) {
    cin >> a[i];
  }
  sort(a.rbegin(), a.rend());
  vector<int> flag(a.size(), 0);
  int cur = a[0];
  cout << a[0] << " ";
  for (int i = 1; i < n; ++i) {
    int max_idx = 0;
    int max_v = 0;
    for (int j = 1; j < n; ++j)
      if (!flag[j]) {
        if (max_v < gcd(cur, a[j])) {
          max_v = gcd(cur, a[j]);
          max_idx = j;
        }
      }
    cur = gcd(cur, a[max_idx]);
    cout << a[max_idx] << " ";
    flag[max_idx] = 1;
  }
  cout << endl;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

Alexander is a well-known programmer. Today he decided to finally go out and play football, but with the first hit he left a dent on the new Rolls-Royce of the wealthy businessman Big Vova. Vladimir has recently opened a store on the popular online marketplace "Zmey-Gorynych", and offers Alex a job: if he shows his programming skills by solving a task, he'll work as a cybersecurity specialist. Otherwise, he'll be delivering some doubtful products for the next two years.

You're given n positive integers a_1, a_2, ..., a_n. Using each of them exactly at once, you're to make such sequence b_1, b_2, ..., b_n that sequence c_1, c_2, ..., c_n is lexicographically maximal, where c_i=GCD(b_1,...,b_i) - the greatest common divisor of the first i elements of b. 

Alexander is really afraid of the conditions of this simple task, so he asks you to solve it.

A sequence a is lexicographically smaller than a sequence b if and only if one of the following holds:

  * a is a prefix of b, but a ≠ b;
  * in the first position where a and b differ, the sequence a has a smaller element than the corresponding element in b.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^3). Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^3) — the length of the sequence a.

The second line of each test case contains n integers a_1,...,a_n (1 ≤ a_i ≤ 10^3) — the sequence a.

It is guaranteed that the sum of n over all test cases does not exceed 10^3.

Output

For each test case output the answer in a single line — the desired sequence b. If there are multiple answers, print any.

Example

Input


7
2
2 5
4
1 8 2 3
3
3 8 9
5
64 25 75 100 50
1
42
6
96 128 88 80 52 7
5
2 4 8 16 17


Output


5 2 
8 2 1 3 
9 3 8 
100 50 25 75 64 
42 
128 96 80 88 52 7 
17 2 4 8 16 

Note

In the first test case of the example, there are only two possible permutations b — [2, 5] and [5, 2]: for the first one c=[2, 1], for the second one c=[5, 1].

In the third test case of the example, number 9 should be the first in b, and GCD(9, 3)=3, GCD(9, 8)=1, so the second number of b should be 3.

In the seventh test case of the example, first four numbers pairwise have a common divisor (a power of two), but none of them can be the first in the optimal permutation b.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int d4i[4] = {-1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
string to_string(char c) { return string(1, c); }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(vector<bool> v) {
  string res;
  for (int i = (0); i < ((int)(v).size()); ++i) res += char('0' + v[i]);
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res;
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return 31 - __builtin_clz(x); }
const long long MOD = 1e9 + 7;
const int MX = 1e5 + 5;
int tree[1];
int sum(int k) {
  int a = 0;
  while (k >= 1) {
    a += tree[k];
    k -= k & -k;
  }
  return a;
}
void add(int k, int x) {
  while (k <= MX) {
    tree[k] += x;
    k += k & -k;
  }
}
vector<int> adj[MX];
int depth[MX];
int diam;
int dfs(int u, int p) {
  int len = 0;
  for (int& v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      int cur = 1 + dfs(v, u);
      ckmax(diam, cur + len);
      ckmax(len, cur);
    }
  return len;
}
int dp[205][205][205] = {0};
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = (0); i < (n); ++i) {
    cin >> a[i];
  }
  sort(a.rbegin(), a.rend());
  vector<int> flag(a.size(), 0);
  int cur = a[0];
  cout << a[0] << " ";
  for (int i = 1; i < n; ++i) {
    int max_idx = 0;
    int max_v = 0;
    for (int j = 1; j < n; ++j)
      if (!flag[j]) {
        if (max_v < gcd(cur, a[j])) {
          max_v = gcd(cur, a[j]);
          max_idx = j;
        }
      }
    cur = gcd(cur, a[max_idx]);
    cout << a[max_idx] << " ";
    flag[max_idx] = 1;
  }
  cout << endl;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

```