Give you a
in-order traversal of a binary Tree. Please find the minimum pre-order
traversal of the tree.

We compare
pre-order by their alphabet order. For example:

If two pre-order
are: {6, 4, 2, 3, 1, 5}, {6, 1, 2, 3, 5, 4},

Since 6 = 6, 4
> 1, the second one is smaller.

First line is an
integer T, which is the number of test cases. (1 <= T <= 10)

For each test
case, there will be an integer in a single line N (1 <= N <= 50000). N is
the number of nodes. The nodes are numbered from 1 to N.

Then there will be
one line. Which is the in-order traversal of the Tree.

Print
the smallest pre-order traversal in a single line.