Recently Zippy received four stacks, named A B C D respectively. Firstly, there are n elements in stack A (the element sequence is a permutation of 1..n), and stack B C D are empty. He can do four types of operations:

• operation a: push the top element of stack A to stack B (if stack A is not empty, this operation can be done.)
• operation b: push the top element of stack B to stack D (if stack B is not empty, this operation can be done.)
• operation c: push the top element of stack A to stack C (if stack A is not empty, this operation can be done.)
• operation d: push the top element of stack C to stack D (if stack C is not empty, this operation can be done.)

He can do 2*n operations in total. Obviously, there are n elements in stack D after he did the 2*n operations. Then he take out the top element in stack D one by one. If the first element he takes out is n, the second is n-1, ... the last is 1, he will be very happy. Also, he wants to make the operation sequence he did lexicographic smallest.

Input

First line is a number t, which is the number of testcases. 

Then following t testcases. For each test case, the first line contains a number n, which denotes the number of the elements in stack A. The second line contains n numbers, separated by a space, which are the elements in stack A, from top to the bottom.

You can be sure that the sum of all n does not exceed 200000, and each n is not bigger than 100000.

Output

For each case, output a line. If there exists an answer, output the lexicographic smallest one (the operations Zippy does, separated by a space). If not, output 0.

Example

Input:
2
4
1 3 4 2
4
2 3 4 1

Output:
a b a c a b b d
0