解题思路

先把操作本质看清楚。

一次操作可以选择两个下标 $i,j$，如果 $a_i \mid a_j$ 或 $a_j \mid a_i$，就可以交换这两个位置上的数。 也就是说，能直接交换的两个数，必须满足“可整除”关系。

进一步考虑：

题目内容

给定一个长度为 $n$ 的序列 $a$，其中第 $i$ 个元素的值为 $a_i$。现在小苯可以对序列进行任意次如下操作：

• 选择两个不同的下标 $i, j\ (1 \le i, j \le n, i \ne j)$，且满足 $a_i$ 与 $a_j$ 为倍数关系（即 $a_i | a_j$ 或 $a_j | a_i$），然后交换 $a_i$ 和 $a_j$。（其中 $|$ 表示整除符号。）

你的任务就是求出，在以上操作可以进行任意次的前提下，最小化 $a$ 的字典序，并输出此时的 $a$。

【名词解释】 数组的字典序比较：从左到右逐个比较两个数组的元素。如果在某个位置上元素不同，比较这两个元素的大小，元素大的数组字典序也大。如果一直比较到其中一个数组结束，则长度较短的数组字典序更小。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1 \le T \le 10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行一个整数 $n\ (1 \le n \le 5 \times 10^5)$，表示序列 $a$ 的长度。
• 第二行 $n$ 个整数 $a_i\ (1 \le a_i \le n)$，表示序列 $a$。

除此之外，保证单个测试文件的 $n$ 之和不超过 $10^6$。

输出描述

对于每组测试数据： 在单独的一行输出 $n$ 个整数，表示序列 $a$ 字典序最小的结果。

样例1

输入

2
5
1 4 3 2 5
6
3 4 2 2 6 5

输出

1 2 3 4 5
2 2 3 4 6 5

说明

第一组测试数据： 选择 $i=2,j=4$，满足 $a_i=4,a_j=2$，4是2的倍数，因此可以交换两者；交换后序列变为 $[1,2,3,4,5]$，这是字典序最小的结果。

第二组测试数据： 满足倍数关系的元素可以自由交换，将可交换范围内的最小元素放置在对应位置，最终得到字典序最小的序列 $[2,2,3,4,6,5]$。