题目描述

下雪的午后，江月诗在屋里整理一组数字卡片。这些卡片按当前顺序组成一个包含 $n$ 个正整数的数组 $a$。

定义 $f(a)$ 为数组中元素乘积能够被 $6$ 整除的非空连续子数组数量。也就是说，每对满足 $1\le l\le r\le n$ 的下标对应一个子数组；当

时，该子数组计入 $f(a)$。

例如，$a=[1,6,2]$ 时，符合条件的子数组为 $[6]$、$[1,6]$、$[6,2]$、$[1,6,2]$，因此 $f(a)=4$。

请帮助江月诗重新排列数组中的元素，使 $f(a)$ 最小。若存在多种最优排列，输出任意一种即可。

输入格式

第一行包含一个整数 $t$，表示测试用例数量，满足 $1\le t\le10^4$。

每组测试用例包含两行：第一行为整数 $n$，满足 $1\le n\le2\times10^5$；第二行为 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $1\le a_i\le10^9$。

保证所有测试用例的 $n$ 之和不超过 $2\times10^5$。

输出格式

对每组测试用例，输出重新排列后的 $n$ 个整数，使 $f(a)$ 最小。输出数组必须保留原数组的全部元素及其出现次数。

输入输出样例 1

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

提示/说明

第一组样例输出为 $[12,18,4,7,5,9]$。其中，包含 $12$ 或 $18$ 的连续子数组共有 $11$ 个，另有子数组 $[4,7,5,9]$ 的乘积也能被 $6$ 整除，因此 $f(a)=12$，且不存在更优排列。

本题答案不唯一，其他达到最小 $f(a)$ 的排列也同样正确。