Statement : C. 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.

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$.

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.

Input

5
6
12 7 9 4 18 5
4
3 6 2 8
7
1 10 15 20 3 6 9
5
11 14 21 2 5
3
6 6 6

Output

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

Note

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)$.