Pancake sorting

You are given a stack of $N$ pancakes, where $1 \le N \le 8$. The pancake at the bottom has index $0$ and the pancake at the top has index $N-1$. The size of a pancake is its diameter, a positive integer. All pancakes in the stack have different sizes.

A stack $A$ of $N = 5$ pancakes with sizes 3, 8, 7, 6 and 10 looks like this.

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

You want to sort the stack in descending order, so that the largest pancake sits at the bottom and the smallest sits at the top. Sorting can only be done by a sequence of pancake flips, written flip(i). The flip(i) operation inserts a spatula into the stack, lifts up the pancakes from index $i$ to index $N-1$ and turns them over, so the order of the pancakes from index $i$ to index $N-1$ is reversed.

For example, stack $A$ becomes stack $B$ via flip(0), stack $B$ becomes stack $C$ via flip(3), and stack $C$ becomes stack $D$ via flip(1). The goal is to reach a stack sorted in descending order, like stack $E$, with as few flips as possible.

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 i    A[i]     B[i]     C[i]     D[i]     ...      E[i]

Bill Gates, who founded Microsoft, has published exactly one research paper, and its subject is this pancake sorting problem.

Gates, W. and Papadimitriou, C. Bounds for Sorting by Prefix Reversal. Discrete Mathematics, 27, 47-57, 1979.

Given the starting configuration of $N$ pancakes, compute the minimum number of flips needed to sort them.

The first line contains an integer $T$, the number of test cases. Each of the next $T$ lines holds one test case. A test case starts with the number of pancakes $N$, followed by $N$ integers giving the size of each pancake. The bottom pancake, the one with index $0$, comes first in the sequence.

For each test case, print on one line the minimum number of flips needed to sort that stack. The output therefore has $T$ lines with one integer per line.