Even-Odd Custom Sort

You are given an array of integers and you need to sort it based on the following rules:

• All even numbers appear before all odd numbers.
• The even numbers are sorted in ascending order. That is, if \(a\) and \(b\) are even and \(a < b\), then \(a\) appears before \(b\).
• The odd numbers are sorted in descending order. That is, if \(a\) and \(b\) are odd and \(a > b\), then \(a\) appears before \(b\).

You need to process multiple test cases. For each test case, the first integer is \(N\) which denotes the number of elements in the array, followed by \(N\) integers.

For each test case, print the sorted array as a single line of space-separated integers.

inputFormat

The input is read from stdin and is structured as follows:

T
N_1
a_1 a_2 ... a_(N1)
N_2
a_1 a_2 ... a_(N2)
...
N_T
a_1 a_2 ... a_(N_T)

Where T is the number of test cases, and for each test case, N specifies the number of elements in the array followed by the N integers.

outputFormat

For each test case, output a single line containing the sorted array (according to the rules) as space-separated integers. The output is written to stdout.

## sample

4
7
4 2 9 1 5 6 7
5
10 20 30 25 15
8
1 3 5 7 2 4 6 8
8
7 3 5 8 6 2 4 1

2 4 6 9 7 5 1
10 20 30 25 15
2 4 6 8 7 5 3 1
2 4 6 8 7 5 3 1

</p>