Happy 12 는 12개의 숫자를 2개의 교차하는 링 위에 놓고 링을 돌리면서 맞추는 퍼즐이다.

숫자가 다 맞춰진 상태는 [1,2,3,4,5,6,7,8,9,10,11,12] 이며, 아래 그림과 같다.

모두 6개의 움직임이 가능하다.

• 왼쪽 링을 시계방향으로 회전
• 왼쪽 링을 반시계방향으로 회전
• 오른쪽 링을 시계방향으로 회전
• 오른쪽 링을 반시계방향으로 회전
• 전체 링을 시계방향으로 회전
• 전체 링을 반시계방향으로 회전

숫자가 다 맞춰진 상태에서 전체 링을 반시계방향으로 회전하면 [12,1,2,3,4,5,6,7,8,9,10,11] 으로 되며, 아래 그림과 같다.

임의의 상태의 퍼즐이 주어졌을 때, 숫자가 다 맞춰진 상태로 되돌리기 위해 필요한 최소한의 이동 횟수는 몇 번일까?

힌트: 회전을 통해 만들 수 없는 상태는 없으며, 어떤 상태이든지 초기 상태로 되돌리는데 20번의 이동 미만이 필요하다.

입력

• 첫번째 줄에는 테스트 케이스의 개수 N 이 주어진다. (N <= 100)
• 둘째줄 부터 N 줄에 걸쳐서 각각의 경우가 1~12 까지의 숫자로 주어진다.

출력

입출력 예

입력

2
1 2 3 4 5 6 7 8 9 10 11 12
2 3 4 5 11 12 6 7 8 9 10 1

출력

0
3

출처: ACPC 2011