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 | = d_k , where k=1..3 and (d₁,d₂,d₃,d₄)=(1;3;6;12)
• floor(i/d_k+1)=floor(j/d_k+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