{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e亚历山大是一位著名的程序员。今天他决定出去踢足球,但是在第一次触球时,他在富有的商人大沃瓦的新劳斯莱斯上留下了一个凹痕。弗拉基米尔最近在热门在线市场“Zmey-Gorynych”上开设了一家店铺,他向亚历克斯提供了一份工作:如果他通过解决一个任务展示出他的编程技能,他将成为一名网络安全专家。否则,他将在接下来的两年里运送一些可疑的产品。\u003c/p\u003e\u003cp\u003e给定$$$n$$$个正整数$$$a_1, a_2, \\dots, a_n$$$。使用每个数字\u003cspan class\u003d\"tex-font-style-bf\"\u003e正好一次\u003c/span\u003e,您需要创建一个序列$$$b_1, b_2, \\dots, b_n$$$,使得序列$$$c_1, c_2, \\dots, c_n$$$是\u003cspan class\u003d\"tex-font-style-it\"\u003e字典序最大\u003c/span\u003e的,其中$$$c_i\u003dGCD(b_1,\\dots,b_i)$$$是前$$$i$$$个元素的最大公约数。\u003c/p\u003e\u003cp\u003e亚历山大非常害怕这个简单任务的条件,所以他请你来解决。\u003c/p\u003e\u003cp\u003e如果一个序列$$$a$$$字典序小于另一个序列$$$b$$$,则只有以下情况之一成立:\u003c/p\u003e\u003cul\u003e\u003cli\u003e$$$a$$$是$$$b$$$的前缀,但$$$a \\ne b$$$;\u003c/li\u003e\u003cli\u003e在$$$a$$$和$$$b$$$不同的第一个位置,序列$$$a$$$的相应元素小于序列$$$b$$$中的元素。\u003c/li\u003e\u003c/ul\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e每个测试包含多个测试用例。第一行包含测试用例的数量$$$t$$$($$$1 \\le t \\le 10^3$$$)。接下来是测试用例的描述。\u003c/p\u003e\u003cp\u003e每个测试用例的第一行包含一个整数$$$n$$$($$$1 \\le n \\le 10^3$$$)— 序列$$$a$$$的长度。\u003c/p\u003e\u003cp\u003e每个测试用例的第二行包含$$$n$$$个整数$$$a_1,\\dots,a_n$$$($$$1 \\le a_i \\le 10^3$$$)— 序列$$$a$$$。\u003c/p\u003e\u003cp\u003e保证所有测试用例中$$$n$$$的总和不超过$$$10^3$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,输出一个单独的答案,即所需的序列$$$b$$$。如果有多个答案,则打印任意一个。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\n2\n2 5\n4\n1 8 2 3\n3\n3 8 9\n5\n64 25 75 100 50\n1\n42\n6\n96 128 88 80 52 7\n5\n2 4 8 16 17\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5 2 \n8 2 1 3 \n9 3 8 \n100 50 25 75 64 \n42 \n128 96 80 88 52 7 \n17 2 4 8 16 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在示例的第一个测试用例中,只有两个可能的排列$$$b$$$ — $$$[2, 5]$$$ 和 $$$[5, 2]$$$:对于第一个排列,$$$c\u003d[2, 1]$$$,对于第二个排列,$$$c\u003d[5, 1]$$$。\u003c/p\u003e\u003cp\u003e在示例的第三个测试用例中,数字$$$9$$$应该是$$$b$$$中的第一个数字,而$$$GCD(9, 3)\u003d3$$$,$$$GCD(9, 8)\u003d1$$$,所以$$$b$$$的第二个数字应该是$$$3$$$。\u003c/p\u003e\u003cp\u003e在示例的第七个测试用例中,前四个数字两两有一个公约数(2的幂),但是没有一个可以成为最佳排列$$$b$$$的第一个数字。\u003c/p\u003e"}}]}