题目描述

Kevin 有一个由 $n$ 个正整数组成的数组 $a$。

定义 $f(a)$ 为数组 $a$ 中 所有子数组 的乘积能被 $6$ 整除的个数。
形式化地说，对所有 $1 \le l \le r \le n$，如果子数组 $a_l, a_{l+1}, \dots, a_r$ 的元素乘积是 $6$ 的倍数，则计一个。

Kevin 可以任意重新排列数组 $a$ 中的元素。他想让 $f(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
6
13
2
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)$ 更小的值。