팬케이크 정렬

팬케이크 $N$개가 하나로 쌓여 있고, $1 \le N \le 8$이다. 맨 아래 팬케이크의 인덱스는 $0$, 맨 위 팬케이크의 인덱스는 $N-1$이다. 팬케이크의 크기는 지름이며 양의 정수다. 한 스택에 있는 팬케이크의 크기는 모두 다르다.

크기가 각각 3, 8, 7, 6, 10인 팬케이크 $N = 5$개로 이루어진 스택 $A$는 다음과 같다.

4 (맨 위)      10
3               6
2               7
1               8
0 (맨 아래)     3
-----------------------
인덱스 i     A[i]

이 스택을 내림차순으로 정렬하려고 한다. 가장 큰 팬케이크가 맨 아래에, 가장 작은 팬케이크가 맨 위에 오면 정렬이 끝난다. 단, 정렬은 뒤집기 연산 flip(i)로만 할 수 있다. flip(i)는 인덱스 $i$ 자리에 뒤집개를 넣어 인덱스 $i$부터 $N-1$까지의 팬케이크를 한꺼번에 들어 올린 다음 통째로 뒤집는다. 그래서 인덱스 $i$부터 $N-1$까지의 순서가 역순이 된다.

예를 들어 스택 $A$에 flip(0)을 적용하면 스택 $B$가 되고, $B$에 flip(3)을 적용하면 $C$가 되며, $C$에 flip(1)을 적용하면 $D$가 된다. 목표는 스택 $E$처럼 내림차순으로 정렬된 상태를 최소 뒤집기 횟수로 만드는 것이다.

4 (맨 위)    10  <--   3  <--   8  <--   6                 3
3             6        8  <--   3        7     ...         6
2             7        7        7        3                 7
1             8        6        6  <--   8                 8
0 (맨 아래)   3  <--  10       10       10                10
--------------------------------------------------------------
인덱스 i   A[i]     B[i]     C[i]     D[i]     ...      E[i]

마이크로소프트를 창업한 빌 게이츠가 지금까지 발표한 연구 논문은 한 편뿐인데, 그 주제가 바로 이 팬케이크 정렬이다.

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

팬케이크 $N$개의 처음 배치가 주어지면, 이 스택을 정렬하는 데 필요한 최소 뒤집기 횟수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 팬케이크의 개수 $N$으로 시작하고, 그 뒤에 팬케이크 $N$개의 크기가 이어진다. 크기는 맨 아래 팬케이크, 즉 인덱스가 $0$인 팬케이크부터 차례로 나온다.

각 테스트 케이스마다 그 스택을 정렬하는 데 필요한 최소 뒤집기 횟수를 한 줄에 하나씩 출력한다. 따라서 출력은 정수 하나씩 담긴 $T$개의 줄이 된다.