크레인

배에 실을 상자 $n$개가 부두에 놓여 있다. 상자에는 $1, 2, \ldots, n$번이 붙어 있고, 이 번호가 실어야 하는 순서다. 그런데 운송 과정에서 문제가 생겨 상자가 한 줄로 아무 순서나 놓여 있다. 부두에 빈 자리가 거의 없어서 상자를 덩어리째 맞바꾸는 방법으로만 정렬할 수 있다.

맞바꾸는 일은 크레인이 한다. 크레인은 한 번 움직일 때 길이가 짝수인 연속 구간을 하나 골라 그 구간의 앞쪽 절반과 뒤쪽 절반을 맞바꾼다. 절반 안에서의 순서는 그대로다.

크레인 소프트웨어에는 버그가 있다. 이동 횟수를 세는 계수기가 10진수가 아니라 9진수이고 자릿수도 여섯 개뿐이다. 그래서 $9^6 = 531441$번 움직이면 크레인이 멈추고 정비를 받아야 한다.

상자를 $1, 2, \ldots, n$ 순서로 만드는 데 필요한 최소 이동 횟수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 상자의 개수 $n$ ($1 \le n \le 8$)이 주어진다. 둘째 줄에는 왼쪽부터 놓인 상자의 번호가 $1, 2, \ldots, n$의 순열로 주어진다.

각 테스트 케이스마다 상자를 정렬하는 데 필요한 최소 크레인 이동 횟수를 한 줄에 출력한다. 크레인의 이상한 계수기를 따르지 말고 평소 쓰는 10진수로 적는다.