CF1509A.Average Height

Sayaka Saeki is a member of the student council, which has $n$ other members (excluding Sayaka). The $i$-th member has a height of $a_i$ millimeters.

It's the end of the school year and Sayaka wants to take a picture of all other members of the student council. Being the hard-working and perfectionist girl as she is, she wants to arrange all the members in a line such that the amount of photogenic consecutive pairs of members is as large as possible.

A pair of two consecutive members $u$ and $v$ on a line is considered photogenic if their average height is an integer, i.e. $\frac{a_u + a_v}{2}$ is an integer.

Help Sayaka arrange the other members to maximize the number of photogenic consecutive pairs.

佐藤沙耶香是学生会的一员，学生会中除她之外还有 $n$ 名成员。第 $i$ 名成员的身高为 $a_i$ 毫米。

学年即将结束，沙耶香希望为学生会其他所有成员拍摄一张合影。作为一名勤奋且追求完美的女孩，她希望将所有成员排成一列，使得“上镜的”相邻成员对的数量尽可能多。

若一行中两个相邻成员 $u$ 和 $v$ 的平均身高为整数，即 $\frac{a_u + a_v}{2}$ 为整数，则称该相邻对 $(u, v)$ 是“上镜的”。

请帮助沙耶香安排其余成员，以最大化上镜的相邻成员对的数量。

The first line contains a single integer $t$ ($1\le t\le 500$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2000$) — the number of other council members.

The second line of each test case contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — the heights of each of the other members in millimeters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

第一行包含一个整数 $t$（$1\le t\le 500$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2000$）——其他理事会成员的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$1 \le a_i \le 2 \cdot 10^5$）——其余每位成员的身高（单位：毫米）。

保证所有测试用例中 $n$ 的总和不超过 $2000$。

For each test case, output on one line $n$ integers representing the heights of the other members in the order, which gives the largest number of photogenic consecutive pairs. If there are multiple such orders, output any of them.

对于每个测试用例，在一行中输出 $n$ 个整数，表示其他成员的高度顺序，该顺序使得“上镜的连续对”数量最大。若存在多个满足条件的顺序，输出其中任意一个即可。

In the first test case, there is one photogenic pair: $(1, 1)$ is photogenic, as $\frac{1+1}{2}=1$ is integer, while $(1, 2)$ isn't, as $\frac{1+2}{2}=1.5$ isn't integer.

In the second test case, both pairs are photogenic.

在第一个测试用例中，存在一个上镜的数对：$(1, 1)$ 是上镜的，因为 $\frac{1+1}{2}=1$ 是整数；而 $(1, 2)$ 不是上镜的，因为 $\frac{1+2}{2}=1.5$ 不是整数。

在第二个测试用例中，两个数对都是上镜的。