## 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
```

hide comments tld: 2010-06-06 13:18:17 I think for the case1 6 maybe the best. oh,sorry I got the worng mean of the problem. I konw now. Last edit: 2010-06-06 13:25:02

 Added by: Duc Date: 2005-04-28 Time limit: 2.574s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS PERL6 VB.NET Resource: Based on a problem from acm.uva.es