B. Большой Вова
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Александр — известный в узких кругах программист. Однажды он решил наконец-то выйти на улицу и активно провести время с мячом, но первым же ударом он оставил вмятину на новом Rolls-Royce богатого и влиятельного предпринимателя Большого Вовы. Бизнесмен недавно открыл интернет-магазин на популярной торговой площадке «Змей-Горыныч», и предлагает Саше устроиться на работу: если он продемонстрирует свои способности, решив задачу, то получит должность специалиста по безопасности, а в противном случае — должность курьера.

Вам даны $$$n$$$ целых положительных чисел $$$a_1, a_2, \dots, a_n$$$. Используя каждое из данных чисел ровно 1 раз, Вы должны составить такую последовательность $$$b_1, b_2, \dots, b_n$$$, что последовательность $$$c_1, c_2, \dots, c_n$$$ лексикографически максимальна, где $$$c_i=GCD(b_1,\dots,b_i)$$$ — наибольший общий делитель первых $$$i$$$ чисел последовательности $$$b$$$.

Александр сильно испугался условия этой несложной задачи, и поэтому он просит у Вас помощи.

Последовательность $$$a$$$ лексикографически меньше последовательности $$$b$$$, если и только если выполняется один из следующих пунктов:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в последовательности $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.
Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^3$$$). Описание наборов входных данных приведено ниже.

Первая строка каждого набора данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^3$$$) — длину последовательности $$$a$$$.

Вторая строка каждого набора данных содержит $$$n$$$ целых чисел $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^3$$$) — последовательность $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^3$$$.

Выходные данные

На каждый набор входных данных выведите ответ в отдельной строке — искомую последовательность $$$b$$$. Если существует несколько подходящих последовательностей, выведите любую из них.

Пример
Входные данные
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
Выходные данные
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
Примечание

В первом наборе тестовых данных примера есть всего две возможные перестановки $$$b$$$: $$$[2, 5]$$$ и $$$[5, 2]$$$. В первом случае $$$c=[2, 1]$$$, во втором $$$c=[5, 1]$$$.

В третьем наборе тестовых данных примера число $$$9$$$ должно идти первым в $$$b$$$, а $$$GCD(9, 3)=3$$$, $$$GCD(9, 8)=1$$$, поэтому вторым в $$$b$$$ идёт число $$$3$$$.

В седьмом наборе тестовых данных примера первые четыре числа попарно имеют общий делитель (степень двойки), однако ни одно из них не может идти первым в оптимальной перестановке $$$b$$$.