## EOPERA - Exchange Operations

no tags

Given a sequence of 12 numbers consisting of 0 and the first 11 natural numbers. Suppose number 0 is in the i-th position of the sequence (positions are numbered from 0 to 11). You can swap it with the number in the j-th position if the following conditions hold:

• | i – j | = dk , where k=1..3 and (d1,d2,d3,d4)=(1;3;6;12)
• floor(i/dk+1)=floor(j/dk+1)

Your task is to find the minimum number of exchange operations required to sort the sequence in increasing order.

### Input

The first line of the input file contains an integer representing the number of test cases to follow. Each test case contains a sequence of twelve numbers consisting of 0,1,2,..,11, separated by single space. You can assume that the given sequence can always be sorted in increasing order by using the exchange operations

### Output

For each test case, output the minimum number of exchange operations required to sort the given sequence in increasing order.

### Example

```Input:
2
1 10 2 3 0 5 7 4 8 6 9 11
6 4 1 0 3 5 9 7 2 10 11 8

Output:
8
9
```