Bojan and Mile are playing an interesting game with numbers. The game is played with several cards that have the digits 0-9 written on them (one digit on each card). The goal of the game is to create the largest possible number that can be obtained using the digits written on the cards, but that doesn't contain two adjacent digits that are of the same parity (that is, they can't both be even or both be odd).

(Note: An integer is considered even if it is 'evenly divisible' by two, and odd otherwise. We consider the digit 0 to be even.)

For example, using cards with digits 1, 2 and 3, one can create the numbers 1, 2, 3, 12, 21, 23, 32, 123 and 321 but not 13, 31, 132, 213, 231 or 312 (because it is not allowed to have two odd digits [1 and 3] next to each other). Similarly, using cards with digits 6, 8, 7 and 8, one can create the numbers 67, 678, 878, etc, but, for example, not the number 8786 (because it contains two even digits in a row).

Since Bojan really wants to beat Mile, he decided to cheat and is now asking you to write a program that will find and print the largest possible number that can be created.

Input

The first line of input contains one positive integer T (1 <= T <= 100), the number of test cases.

Each test case starts with a line that contains exactly one integer N (1 <= N <= 8), the number of cards. The following line contains N digits (0-9), separated by single spaces, which specify the digits written on top of each card.

Output

For each test case, on a separate line, output the largest possible number that can be created.

Constraints

Time limit: 2 seconds
Memory limit: 64 megabytes

Examples

input
2
3
5 6 7
4
6 8 7 8

output
765
878