Sorting the Bookshelf

Alex and Bob are brothers, and both of them love reading. Their tastes in books are very different, so each keeps his own books apart from the other's. Their father thinks that putting the books together will get the brothers to lend books to each other, so today he bought a one row bookshelf and placed every book of his two sons on it in a random order. He also labeled each position of the shelf with the owner of the book standing there ('Alex' or 'Bob').

Alex and Bob were outside and knew nothing about this. When they came back and saw the mess, they decided to sort the books right away.

Every book has a worth, given as an integer. A book with an odd worth belongs to Alex, and a book with an even worth belongs to Bob. Alex arranges his books from left to right in increasing order of worth, and Bob arranges his books from left to right in decreasing order of worth. A worth may be negative, and a negative number has the same parity as its absolute value.

The labels stay where they are. After the sorting, the owner of the book at each position must still match the label at that position.

You are given the worths $s_0, s_1, \ldots, s_{N-1}$ of the books currently on the shelf, from left to right. Find the sequence of worths after the sorting.

The first line contains the number of test cases $T$. Each test case begins with a line containing $N$, the number of books on the shelf. The next line contains the worths $s_0, s_1, \ldots, s_{N-1}$ in left to right order, separated by spaces.

Limits

• $1 \le T \le 30$
• $1 \le N \le 1000$
• $-1000 \le s_i \le 1000$

For each test case, print one line containing "Case #$X$: " followed by the worths after the sorting, $t_0, t_1, \ldots, t_{N-1}$, in left to right order and separated by spaces. $X$ is the test case number, starting from 1.