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

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