Crane

There are $n$ crates waiting to be loaded onto a ship. The crates are numbered $1, 2, \ldots, n$, and the numbers give the loading order. Something went wrong in transit, so the crates now stand in a row in an arbitrary order. The dock has very little free space, so the only way to sort them is to swap whole blocks of crates.

A crane does the swapping. In one move the crane picks a contiguous interval of crates whose length is even, then exchanges the first half of the interval with the second half. The order inside each half stays the same.

The crane's software has a bug: the move counter is a 9-based integer (not 10-based, as you might think) with at most 6 digits. The crane therefore stops working and has to be serviced after $9^6 = 531441$ moves.

Find the smallest number of crane moves that puts the crates in the order $1, 2, \ldots, n$.

The first line of input contains the number of test cases $T$. The descriptions of the test cases follow.

Each test case starts with a line holding an integer $n$ ($1 \le n \le 8$), the number of crates. The next line holds a permutation of $1, 2, \ldots, n$, the crate numbers from left to right.

For each test case print a single line containing the minimum number of crane moves needed to sort that row of crates. Do not follow the crane's strange software design, use the standard decimal numeral system.