C. Snowfall

Yousef has given you an array 𝑎

 of 𝑛

 positive integers.

Let 𝑓(𝑎)

 denote the number of subarrays

∗

 of 𝑎

 whose product is divisible by 6

.

More formally, for every pair of indices 𝑙

 and 𝑟

 such that 1≤𝑙≤𝑟≤𝑛

, consider the subarray 𝑎

𝑙

,𝑎

𝑙+1

,…,𝑎

𝑟

. This subarray is counted if the product of its elements is divisible by 6

.

For example, if 𝑎=[1,6,2]

, then the subarrays whose products are divisible by 6

 are [6]

, [1,6]

, [6,2]

, and [1,6,2]

, so 𝑓(𝑎)=4

.

Your task is to reorder the elements of the array 𝑎

 so that 𝑓(𝑎)

 is minimized. If there are multiple ways to do this, you may output any of them.

∗

An array 𝑏

 is a subarray of an array 𝑎

 if 𝑏

 can be obtained from 𝑎

 by deleting several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.

Input

The first line of the input contains an integer 𝑡

 (1≤𝑡≤10

4

) — the number of test cases.

The first line of each test case contains an integer 𝑛

 (1≤𝑛≤2⋅10

5

) — the size of the array.

The second line of each test case contains 𝑛

 integers 𝑎

1

,𝑎

2

,…,𝑎

𝑛

 (1≤𝑎

𝑖

≤10

9

) — the elements of the array.

It is guaranteed that the sum of 𝑛

 over all test cases does not exceed 2⋅10

5

.

Output

For each test case, output the array after reordering it in such a way that 𝑓(𝑎)

 is minimized. If there are multiple answers, you may output any of them.

Example

Input

Copy

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

Copy

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 𝑎=[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, 𝑓(𝑎)=12

. It can be proven that no other arrangement yields a smaller value of 𝑓(𝑎)

.