CF2227C.Snowfall

Yousef has given you an array $a$ of $n$ positive integers.

Let $f(a)$ denote the number of subarrays$^{\text{∗}}$ of $a$ whose product is divisible by $6$.

More formally, for every pair of indices $l$ and $r$ such that $1 \le l \le r \le n$, consider the subarray $a_l, a_{l+1}, \dots, a_r$. This subarray is counted if the product of its elements is divisible by $6$.

For example, if $a = [1, 6, 2]$, then the subarrays whose products are divisible by $6$ are $[6]$, $[1, 6]$, $[6, 2]$, and $[1, 6, 2]$, so $f(a) = 4$.

Your task is to reorder the elements of the array $a$ so that $f(a)$ is minimized. If there are multiple ways to do this, you may output any of them.

$^{\text{∗}}$An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deleting several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.

优素福给了你一个包含 $n$ 个正整数的数组 $a$。

令 $f(a)$ 表示数组 $a$ 中乘积能被 $6$ 整除的子数组$^{\text{∗}}$ 的个数。

更准确地说，对每一对满足 $1 \le l \le r \le n$ 的下标 $l$ 和 $r$，考虑子数组 $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$ 的一个子数组。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

For each test case, output the array after reordering it in such a way that $f(a)$ is minimized. If there are multiple answers, you may output any of them.

对于每个测试用例，输出按某种方式重排后的数组，使得 $f(a)$ 最小。如果存在多个满足条件的答案，你可以输出其中任意一个。

In the first test case, an optimal arrangement is $a = [12, 18, 4, 7, 5, 9]$. The subarrays whose products are divisible by $6$ are:

• $[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]$

Therefore, $f(a) = 12$. It can be proven that no other arrangement yields a smaller value of $f(a)$.

在第一个测试用例中，一种最优排列为 $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)$ 取得更小的值。