EOPERA - Exchange Operations

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

Added by:Jimmy
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

hide comments
2010-06-06 13:18:17 tld
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.