1181 - SCU-A:: HUST Online Judge

1181 - SCU-A

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 39

Solved: 16

Description

A Young tableau is a 4*4 integers such that each row and column is
sorted in ascending order (rows left-to-right, columns top-to-bottom).

Given a 4*4 table, can you tell me the fewest number of swaps required
to turn the table into a Young tableau.

Input

The first line of the input will be a integer to represent the number of test cases.
For each test case there is 4 lines.
Eash line contains 4 integers.
All of the integers are distinct and between 1 and 16, inclusive.
There is a blank line before each test case.

Output

For each test case output the answer on a single line:
The fewest number of swaps required to turn the table into a Young tableau.

sample input

6

1 3 5 6
2 4 7 8
9 10 11 12
13 14 15 16

16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

7 6 10 5
1 3 2 4
11 9 16 15
13 8 14 12

2 1 3 4
5 6 7 8
9 10 11 12
13 14 15 16

16 2 3 4
5 6 7 8
9 10 11 12
13 14 15 1

sample output

hint

source

SCUPC