Yousef 给了你一个由 ~n~ 个正整数组成的数组 ~a~。

设 ~f(a)~ 表示 ~a~ 中乘积可被 6 整除的子数组~^{\text{∗}}~的数量。

更正式地，对于每对下标 ~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)~ 最小化。如果有多个答案，你可以输出其中任意一个。

样例

输入

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

输出

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)~ 值。