题目描述

出题人 Alice 给了 Bob $n$ 题用于联测。

由于题目乱序会被扣钱，所以 Bob 不能直接随机排序。具体而言，每一题有一个参数 $a_i$ 表示题目难度（$a_i$ 为正整数且 $1\le a_i\le 10^8$，不保证互不相同），每次操作仅能交换相邻两道题目 $i,i+1$ 且要求 $a_i,a_{i+1}$ 互质。

Bob 希望题目难度递减，因此他会进行若干次操作，使得最终题目难度序列 $a$ 字典序最大。但是他拿到的题目顺序是 Alice 决定的，而 Alice 希望题目难度尽量递增，所以她会重排题目使得 Bob 最终达到的难度序列 $a$ 字典序最小。求最优策略下的序列 $a$。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每一组数据：

第一行为一个正整数 $n$，表示题目数量。

第二行 $n$ 个正整数 $a_1,a_2,\cdots a_n$ 表示 $n$ 道题目的难度。注意由于 Alice 可以对题目任意重排，输入中 a 的顺序没有意义。

输出格式

对于每组数据，输出一行 $n$ 个正整数，表示最优策略下最终的序列 $a$。

样例

ex_automaton1.in
2
5
1 2 3 4 5
4
2 3 4 6
ex_automaton1.out
5 3 2 4 1
2 4 6 3

ex_npc2.in/out 见下发文件。

数据范围

对于所有测试点，满足 $1\le T\le 5$, $3 \le n \le 2000$, $1 \le a_i \le 10^8$。

以下 $id$ 为测试点编号。