책 정렬

라이덴 대학교 도서관에는 책이 수백만 권 있다. 학생은 빌리고 싶은 책이 있으면 보통 온라인 대출 신청서를 낸다. 그 책이 대출 가능하면 다음 날 대출 창구에서 받아 간다. 요즘 이 도서관에서 책을 빌리는 방식이다.

도서관에는 예전 방식이 그대로 남아 있는 부서가 하나 있다. 책장이 빽빽한 이곳에서는 학생이 직접 돌아다니며 마음에 드는 책을 고르고, 등록만 하면 최대 3주 동안 집에 가져갈 수 있다.

그런데 학생이 책장에서 책을 꺼내 살펴보고는 읽지 않기로 하고 도로 꽂아 두는 일이 자주 있다. 이 마지막 단계를 꼼꼼히 하지 않는 학생이 있다. 책마다 고유한 식별 번호가 있고 책장의 책은 이 번호 순서로 꽂혀 있는데, 살펴보기만 한 책을 엉뚱한 자리에 꽂는 것이다. 책장은 제대로 찾아가지만 책장 안에서 자리가 틀린다.

한편 온라인 목록에서 찾은 고유 식별 번호로 빌릴 책을 찾는 학생도 있다. 이런 학생에게는 책이 정말 번호순으로 꽂혀 있는지가 중요하다. 사서에게도 중요하다. 대출되지도 않았는데 없어진 책, 즉 도난당한 책을 가려내기가 훨씬 쉬워지기 때문이다.

그래서 사서는 매주 이 부서를 돌며 책장마다 책을 정렬한다. 책장 하나를 정렬하는 일은 할 만하지만 손이 꽤 간다. 사서는 여러 알고리즘을 따져 본 끝에 자기에게 가장 편한 방법으로 자리 바꾸기 정렬을 골랐다. 책이 정렬될 때까지 다음을 반복한다.

1. 나란히 붙어 있는 책 몇 권을 한 덩어리로 통째로 꺼낸다.
2. 그렇게 생긴 빈자리의 왼쪽이나 오른쪽에 붙어 있는 다른 덩어리를 그 빈자리로 옮긴다.
3. 처음에 꺼낸 덩어리를 두 번째 덩어리가 비우고 간 자리에 넣는다.

이 세 단계를 한 번 수행하는 것이 자리 바꾸기 한 번이다.

아래 그림은 각 단계를 보여 준다. X는 첫 번째 덩어리, Y는 두 번째 덩어리다.

사서는 일을 최대한 줄이고 싶다. 즉 책장마다 정렬에 필요한 자리 바꾸기 횟수를 최소로 하려고 한다. 특히 자리 바꾸기 4번 안에 책장의 책을 정렬할 수 있는지 알고 싶어 한다. 사서에게 답을 알려 주자.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 정수 $n$ 하나가 주어진다. 어떤 책장에 꽂힌 책의 수이며 $1 \le n \le 15$이다.
• 한 줄에 $1, 2, \ldots, n$을 어떤 순서로 나열한 정수 $n$개가 공백 하나로 구분되어 주어진다. 지금 책장에 꽂혀 있는 순서대로 적은 책 $n$권의 고유 식별 번호다.

각 테스트 케이스마다 다음을 한 줄에 출력한다.

• 고유 식별 번호가 커지는 순서가 되도록 책을 정렬하는 데 필요한 자리 바꾸기 최소 횟수를 $T$라고 할 때, $T \le 4$이면 그 최솟값 $T$.
• 정렬에 자리 바꾸기가 5번 이상 필요하면 5 or more.