题目内容

仓储系统把 $n$ 个货位上的规格编号排成序列 $a_1, a_2, \dots, a_n$，每个编号满足 $1 \le a_i \le n$。调度规则允许：选择两个不同货位 $i, j$，若它们的规格存在整除关系（$a_i \mid a_j$ 或 $a_j \mid a_i$），就可以把这两个位置上的编号对调。该操作可做任意次。仓管员希望在合法对调之后，得到字典序最小的规格序列并输出。

数组字典序：从左到右比较，在第一个不同位置上数值更小的一方更小。

约束：测试组数不超过 100000，单组 $n$ 不超过 500000，所有组 $n$ 之和不超过 1000000，且 $1 \le a_i \le n$。

输入描述

每个测试文件包含多组数据。第一行一个整数 $T$，表示组数。 每组第一行一个整数 $n$，第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。 保证 $1 \le T \le 100000$，$1 \le n \le 500000$，$1 \le a_i \le n$，且所有组 $\sum n \le 1000000$。

输出描述

对每组数据输出一行 $n$ 个整数，表示操作后字典序最小的规格序列。

样例1

输入

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

输出

1 2 3 4
1 2 3 4 5 6 7

说明

第一组出现 1,2,3,4，它们处于同一整除连通块，按位置回填升序后得到 1 2 3 4。

第二组存在 1，它整除所有数，因此全部元素属于同一连通块，排序后得到 1 2 3 4 5 6 7。

样例2

输入

1
1
1

输出

1

说明

长度为 1，无需交换，输出 1。

样例3

输入

1
3
3 3 1

输出

1 3 3

说明

1 与 3 满足整除关系，同一连通块，排序后为 1 3 3。