Rearrange Array

Given an array of integers, rearrange the elements such that no two consecutive elements are the same. If it is not possible to produce such an arrangement, output "Not possible".

Mathematically, given an array (a_0, a_1, \dots, a_{n-1}), find a permutation (p) such that for every (1 \le i < n), (a_{p(i)} \ne a_{p(i-1)}). If no valid permutation exists, print (\texttt{Not\ possible}).

Please use standard input (stdin) for input and standard output (stdout) for output.

inputFormat

The input begins with an integer (T) ((1 \le T \le 100)), representing the number of test cases. For each test case, the first line contains an integer (N) (the number of elements), and the second line contains (N) space-separated integers.

outputFormat

For each test case, output a single line. If a valid rearrangement exists, print the rearranged array as space‐separated integers; otherwise, print (\texttt{Not\ possible}). Each test case’s result should be printed on a new line.## sample

1
4
1 1 2 2

1 2 1 2