Sorting Game

문제 정보

문제

중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는, 3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤, 전체를 뒤집어 정렬할 수도 있지만, 4 1 2 를 먼저 뒤집고, 3 2 1 을 다시 뒤집으면 두 번만의 연산으로 정렬할 수도 있다.

정렬을 위해 뒤집기 연산을 최소 몇 번 해야 하는지를 계산하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 1000) 이 주어진다. 각 테스트 케이스의 첫 줄에는 수열의 길이 N (1 <= N <= 8) 이 주어진다. 다음 줄에 N개의 정수로 각 수열의 원소들이 순서대로 주어진다. 한 수열에 같은 수가 두 번 출현하지 않는다고 가정해도 좋다. 모든 수는 1부터 1백만 사이의 정수이다.

출력

각 테스트 케이스마다 입력을 정렬하기 위해 필요한 최소 뒤집기 연산의 수를 출력한다.

예제 입력

3
8
1 2 3 4 8 7 6 5
4
3 4 1 2
3
1 2 3

예제 출력

1
2
0

노트

15개의 댓글이 있습니다.