Alexander是一位著名的程序员。今天,他终于决定出去踢足球,但第一击就在富商大沃瓦的新劳斯莱斯上留下了凹痕。弗拉基米尔最近在流行的在线市场“Zmey-Gorynych”上开设了一家商店,并为亚历克斯提供了一份工作:如果他通过解决任务来展示他的编程技能,他将担任网络安全专家。否则,他将在未来两年内交付一些可疑的产品。
给你 $$$n$$$ 正整数 $$$a_1, a_2, \dots, a_n$$$。一次完全使用它们中的每一个,您将创建这样的序列 $$$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$$$。如果有多个答案,请打印其中一个。
示例
输入 #1
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
输出 #1
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$$$。
在示例的第七个测试用例中,前四个数字成对具有公约数(2 的幂),但它们都不能成为最佳排列 $$$b$$$ 中的第一个。