Bookshelf Sorting

Alex and Bob are brothers and both of them like reading. Their tastes in books are very different, so each of them keeps his own books separately. Their father thinks that putting the books together makes it easier for the brothers to share them. Today he bought a one row bookshelf and placed all of his sons' books on it in random order. He also wrote on every position of the shelf the name of the owner of the book that sits there, either Alex or Bob.

Alex and Bob were outside and did not know what their father had done. When they came back, they saw the problem. Each of them used to arrange his books in his own order, and now the shelf is a mess. They have 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.

At the same time the brothers do not want to move the labels. After the sorting is finished, the owner of each book must match the label at its position.

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

The first line contains one integer $T$, the number of test cases. Each test case starts with a line containing one integer $N$, the number of books on the shelf. The next line contains $N$ integers separated by spaces, the worths $s_0, s_1, \dots, s_{N-1}$.

Limits

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

For each test case, print one line. The line starts with Case #X: , where $X$ is the case number starting from 1, and is followed by $t_0, t_1, \dots, t_{N-1}$ in order, separated by single spaces.