Yousef 给了你一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。
设 $$$f(a)$$$ 表示 $$$a$$$ 的子数组 $$$^{\text{∗}}$$$ 的数量,其中 产品 可以被 $$$6$$$ 整除。
更正式地说,对于每对索引 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l \le r \le n$$$,考虑子数组 $$$a_l, a_{l+1}, \dots, a_r$$$。如果该子数组的元素的乘积能被 $$$6$$$ 整除,则该子数组被计数。
例如,如果 $$$a = [1, 6, 2]$$$,则乘积可被 $$$6$$$ 整除的子数组为 $$$[6]$$$、$$$[1, 6]$$$、$$$[6, 2]$$$ 和 $$$[1, 6, 2]$$$,因此 $$$f(a) = 4$$$。
您的任务是对数组 $$$a$$$ 的元素重新排序,以使 $$$f(a)$$$ 最小化。如果有多种方法可以做到这一点,您可以输出其中任何一种。
$$$^{\text{*}}$$$数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素从 $$$a$$$ 获得。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,以最小化 $$$f(a)$$$ 的方式重新排序后输出数组。如果有多个答案,您可以输出其中任何一个。
示例
输入复制
5612 7 9 4 18 543 6 2 871 10 15 20 3 6 9511 14 21 2 536 6 6
输出复制
12 18 4 7 5 9 2 8 3 6 6 10 20 1 15 3 9 21 5 11 2 14 6 6 6
注意
在第一个测试用例中,最佳排列是 $$$a = [12, 18, 4, 7, 5, 9]$$$。其乘积可被 $$$6$$$ 整除的子数组是:
- $$$[12]$$$
- $$$[18]$$$
- $$$[12, 18]$$$
- $$$[18, 4]$$$
- $$$[12, 18, 4]$$$
- $$$[18, 4, 7]$$$
- $$$[12, 18, 4, 7]$$$
- $$$[18, 4, 7, 5]$$$
- $$$[4, 7, 5, 9]$$$
- $$$[12, 18, 4, 7, 5]$$$
- $$$[18, 4, 7, 5, 9]$$$
- $$$[12, 18, 4, 7, 5, 9]$$$
因此,$$$f(a) = 12$$$。可以证明,没有其他安排会产生更小的 $$$f(a)$$$ 值。