Sayaka Saeki is a member of the student council, which has n other members (excluding Sayaka). The i-th member has a height of ai 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. au+AV2 is an integer.

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

Input

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

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

The second line of each test case contains n integers a1, a2, ..., an

?(1≤ai≤2?105)? — 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.

Output

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.

------------------------------------------------------------

佐伯沙耶香是學(xué)生會(huì)成員，學(xué)生會(huì)共有n名成員（不包括沙耶香）。 第i個(gè)構(gòu)件的高度為ai 毫米。

學(xué)年結(jié)束了，沙耶香想給學(xué)生會(huì)的所有其他成員拍一張照片。 作為一個(gè)努力工作、追求完美的女孩，她希望將所有成員排成一排，使上鏡的連續(xù)對(duì)數(shù)盡可能多。

如果一條線上的兩個(gè)連續(xù)成員 u 和 v 的平均高度是整數(shù)，即 au+AV2 是整數(shù)，則認(rèn)為它們是上鏡的。

幫助沙耶香安排其他成員，使上鏡的連續(xù)配對(duì)數(shù)量最大化。

輸入

第一行包含一個(gè)整數(shù) t (1≤t≤500) — 測(cè)試用例的數(shù)量。

每個(gè)測(cè)試用例的第一行包含一個(gè)整數(shù)n（2≤n≤2000）——其他理事會(huì)成員的數(shù)量。

每個(gè)測(cè)試用例的第二行包含n個(gè)整數(shù)a1, a2, ..., an

? (1≤ai≤2?105) — 其他每個(gè)構(gòu)件的高度（以毫米為單位）。

保證所有測(cè)試用例的n總和不超過(guò)2000。

輸出

對(duì)于每個(gè)測(cè)試用例，在一行上輸出 n 個(gè)整數(shù)，表示順序中其他成員的高度，這給出了上鏡連續(xù)對(duì)的最大數(shù)量。 如果有多個(gè)這樣的訂單，則輸出其中任何一個(gè)。

-----------------------------

先把奇數(shù)的元素排完，然后排偶數(shù)的元素即可；

下面是代碼：