Pancake (Extreme)

Problem Description

Time Limit: 1s
Memory Limit: 256 MB

This problem has been posed in Singapore NOI 2012, but wait... there is an (EXTREME) tag in this problem title :O.

You are given a stack of N pancakes, where 1 ≤ N ≤ 10.
The pancake at the bottom and at the top of the stack has index 0 and index N-1, respectively.
The size of a pancake is its diameter which is a positive integer.
All pancakes in the stack have different sizes.
A stack A of N = 5 pancakes with size 3, 8, 7, 6, and 10 can be visualized as:

4 (top)       10
3             6
2             7
1             8
0 (bottom)    3
-----------------------
index         A

We want to sort the stack in descending order, that is, the largest pancake is at the bottom and the smallest pancake is at the top.
To make the problem more real-life like, sorting a stack of pancakes can only be done by a sequence of pancake 'flips', denoted by flip(i).
The flip(i) operation inserts a spatula into the stack, lifts up pancakes from index i to index N-1 and flips them.
As a result, the position of the pancakes from index i to N-1 are reversed.

For example, stack A can be transformed to stack B via flip(0), i.e. inserting a spatula and flipping the pancakes from index 0 to 4.
Stack B can be transformed to stack C via flip(3).
Stack C can be transformed to stack D via flip(1), and so on.
Our target is to make the stack sorted in descending order, i.e. we want the stack to be like stack E.

4 (top)       10 <--    3  <--    8  <--    6                 3
3             6         8  <--    3         7        ...      6
2             7         7         7         3                 7
1             8         6         6  <--    8                 8
0 (bottom)    3  <--    10        10        10                10
-----------------------------------------------------------------
index         A         B         C         D        ...      D

Bill Gates (Microsoft founder, former CEO, and current chairman) wrote only one research paper so far, and it is about this pancake sorting.
Gates, W. and Papadimitriou, C. Bounds for Sorting by Prefix Reversal, Discrete Mathematics, 27, 47-57, 1979.

In this question, given the starting configuration of N pancakes, you task is to compute the minimum number of flips required to sort them.

Input

The first line of input contains an integer TC which is the number of test cases (1 ≤ TC ≤ 10000).
Each of the next TC lines corresponding to a test case.
Each test case starts with the number of pancakes N, three blank spaces, and then followed by N 32-bit signed integers corresponding to the size of each pancake.
The bottom pancake (i.e. the pancake with index 0) appears first in the sequence.

Output

For each test case, output in one line the minimum number of flips required to sort the test case.

Limits

Subtask 1 (1%): The minimum number of flips is not constrained. The pancake sizes ranges from 1 to 1000000 and we have 1 ≤ TC ≤ 10000. However, N ≤ 8.

Subtask 2 (1%): The minimum number of flips is not constrained. The pancake sizes ranges from 1 to 1000000 and we have 1 ≤ TC ≤ 10000. However, N ≤ 10.

Subtask 3 (98%): Killer testcase. Good luck!

Sample Input

3
5    555555 111111 222222 444444 333333
8    1000000 999999 999998 999997 999996 999995 999994 999993
5    3 8 7 6 10

Sample Output

2
0
4

Explanation

The first input stack can be sorted in descending order by 2 flips: flip(3) then flip(1).

The second input stack is already sorted in descending order, so no flip is needed.

The third input stack (which is the example given in the task description) can be sorted in 4 flips by the following two possible sequences:
Solution 1: flip(0), flip(1), flip(2), flip(1): 4 flips.
Solution 2: flip(1), flip(2), flip(1), flip(0): also 4 flips.
There is no way to sort using less than 4 flips, and thus 4 is the minimum possible.