Problem B: Happy 12

Happy 12 is a puzzle consisting of 12 tokens placed on two intersecting rings. The initial configuration is [1,2,3,4,5,6,7,8,9,10,11,12] and is shown below:

We have 6 moves available:

The configuration after the clockwise turn on the left ring is [2,3,4,5,6,12,7,8,9,10,11,1] and is shown below:

The configuration after the counter-clockwise turn on the whole puzzle is [12,1,2,3,4,5,6,7,8,9,10,11] and is also shown below:

Given a configuration of the puzzle, what is the minimum number of moves needed to get the puzzle into the initial configuration?

Note: Every possible configuration can be obtained from the initial configuration using the available moves listed above.
For any configuration of the puzzle, the minimum number of moves to reach it from the initial configuration is less than 20.

Input Format

The input starts with an integer T - the number of test cases (T<=100). T cases follow on each subsequent line, each of them containing a permutation of integers from 1 to 12 - current configuration of the puzzle.

Output Format

For each test case, print on a separate line the minimum number or moves needed to get the puzzle into the initial configuration.

Sample Input

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

Sample Output

0
3

Darko Aleksic
ACPC 2011