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

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

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

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

from math import gcd

t = int(input())
for _ in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    g = max(l)
    out = []
    while l:
        nex = max((gcd(g,l[i]), i) for i in range(len(l)))
        out.append(l.pop(nex[1]))
        g = nex[0]
    print(' '.join(map(str,out)))
        
    


from math import gcd
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)

	answer = []
	answer.append(a.pop(0))
	n -= 1
	gc = answer[0]
	for _ in range(n):
		index = 0
		m = 0
		for i, val in enumerate(a):
			num = gcd(gc, val)
			if num >= m:
				m = num
				index = i
		gc = min(gc, m)
		if gc == 1:
			answer.extend(a)
			break
		else:
			answer.append(a.pop(index))
	print(" ".join(str(num) for num in answer))

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)
for i in ' '*(int(input())):
    n=int(input())
    L=list(map(int,input().split()))
    M=[0]
    MM=[]
    check=[False]*n
    for i in range(n):
        ct=0
        pt=-1
        for j in range(n):
            if not check[j]:
                k=gcd(M[-1],L[j])
                if k>ct:
                    ct=k
                    pt=j
        M.append(ct)
        MM.append(pt)
        check[pt]=True
    for j in MM:print(L[j],end=' ')
    print()

from math import *
from bisect import *
from collections import *
from random import *
from decimal import *
def inp():
    return int(input())
def st():
    return input().rstrip('\n')
def lis():
    return list(map(int,input().split()))
def ma():
    return list(map(int,input().split()))
t=inp()
while(t):       
    t-=1
    n=inp()
    a=lis()
    cur=0
    r=[]
    while(len(a)!=0):
        ind=0
        mi=-1000000000000000
        for i in range(len(a)):
            if(gcd(cur,a[i])>mi):
                mi=gcd(cur,a[i])
                ind=i
        r.append(a[ind])
        cur=gcd(cur,a[ind])
        a.pop(ind)
    print(*r)
        
            
        


import sys
from math import gcd
input = sys.stdin.readline
for _ in range(int(input())):
  N = int(input())
  a = list(map(int, input().split()))
  mx = max(a)
  table = [0] * (mx + 1)
  for x in a: table[x] += 1
  res = [mx]
  table[mx] -= 1
  g = mx
  for _ in range(N - 1):
    y = 0
    for x in range(1, mx + 1):
      if table[x] == 0: continue
      if y == 0 or (gcd(g, x) > gcd(g, y)): y = x
    table[y] -= 1
    res.append(y)
    g = gcd(g, y)
  print(*res)

from math import gcd
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    arr = [(e, e) for e in arr]
    res = []
    while len(arr) > 0:
        arr.sort()
        x = arr.pop()
        res.append(x[1])
        for i in range(len(arr)):
            arr[i] = (gcd(arr[i][0], x[0]), arr[i][1])
    print(*res)


import math
TC = int(input())
for _ in range(TC):
    n = int(input())
    a = list(map(int, input().split()))
    mark = [False] * n
    prev = 0
    for i in range(n):
        idx = 0
        cur = 0
        for j in range(n):
            if mark[j] == True: continue
            if math.gcd(prev, a[j]) > cur:
                cur = math.gcd(prev, a[j])
                idx = j
        mark[idx] = True 
        prev = cur 
        print(a[idx], end = ' ')
    print()