Big Vova
Contest: Codeforces Round 669 (Div. 2)
Difficulty rating: 1300
Tags: brute force, greedy, math, number theory

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, \dots, a_n$$$. Using each of them exactly at once, you're to make such sequence $$$b_1, b_2, \dots, b_n$$$ that sequence $$$c_1, c_2, \dots, c_n$$$ is lexicographically maximal, where $$$c_i=GCD(b_1,\dots,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 \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). Description of the test cases follows.

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

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

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

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

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

Example 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

Editorial:
We'll describe several constructive solutions for this task, differing by the time complexity:
1. $$$O(n^2log A)$$$
Let $$$b$$$ be an empty sequence in the beginning. We'll consequently transfer elements from $$$a$$$ to $$$b$$$ in a certain order.
Let's notice that if we've already transfered $$$(k-1)$$$ elements then we can always choose to the place of $$$b_k$$$ any element $$$a_j$$$ left in $$$a$$$ such that $$$c_k=gcd(b_1,\dots,b_{k-1},a_j)$$$ is maximal. A-priory, if we've fixed the first $$$(k-1)$$$ elements of the sequence, lexicographically greater would be the one in which $$$c_k$$$ is maximal. The particular value of $$$b_k$$$ here doesn't matter: each element $$$c_i$$$ divides all the previous ones, so $$$gcd(b_k, c_j)=gcd(c_k,c_j)$$$ for any $$$j>=k$$$.
So the algorithm is following: let's say that we have auxiliary element of the sequence $$$c_0=0$$$, and $$$gcd(0, k)=k$$$ for any integer $$$k\geq1$$$. Then we make $$$n$$$ iterations: during the $$$i$$$-th one we choose such $$$a_j$$$ (overall elements left in $$$a$$$) that the value of $$$gcd(a_j, c_{i-1})$$$ is maximal, and make $$$b_i=a_j$$$, removing $$$a_j$$$ from the sequence $$$a$$$. The $$$i$$$-th iteration will be passed in $$$O((n-i)log A)$$$, where $$$A$$$ is the greatest possible value in the original $$$a$$$ sequence, $$$log A$$$ is the time complexity of the Euclidean algorithm for searching $$$GCD$$$. Via summing time complexities overall iterations we get summary $$$O(n^2log A)$$$ time complexity of the algorithm.
2. $$$O(Anlog A)$$$
The main idea is the same as in the first solution, but the realisation is different: the main array $$$a$$$ is contained as an array $$$cnt$$$ of size $$$A$$$, where $$$cnt_x$$$ is the amount of elements in $$$a$$$ that are equal to $$$x$$$. Searching for the optimal element $$$b_k$$$ is $$$O(Alog A)$$$ for each of $$$n$$$ iterations, so the summary is $$$O(Anlog A)$$$.
3. $$$O(nlog^2 A)$$$
This solution is based on the following idea: for each $$$i>1$$$ either $$$c_i=c_{i-1}$$$ or $$$2c_i\leq c_{i-1}$$$. That means any possible sequence $$$c$$$ contains $$$O(log A)$$$ different values.
So we do $$$O(log A)$$$ iterations, on each we find the value $$$x$$$ among the elements left in $$$a$$$ that maximizes $$$O(c_k, x)$$$ (where $$$k$$$ is the amount of elements already transfered to $$$b$$$, and $$$c_k=gcd(b_1,\dots,b_k)$$$) and transfer all the elements left in $$$a$$$ of the value equal to $$$x$$$ to the end of $$$b$$$. Each iteration is done in $$$O(n log A)$$$ so the total time complexity is $$$O(n log^2 A)$$$.