Chess War

Time Limit: 1 Second    Memory Limit: 32768 KB

Have you played chess? Oh, It's really an interesting game. As you know, during the game, you can have your chessmen strived with the enemies. Of course, they should follow the fixed rules. For example, the chessman horse is now in the position I, he can only move to the position 1 (or 2, 3 ... 8) showed in the graph next step.

Sundance is a clever and emulative girl who likes playing chess very much, she wants to defeat her enemies totally. You know, it is really a hard work. So she needs to plan carefully.

As a smart girl, she soon comes to a strategy. First she will dispatch her brave horse tour around the whole "world" (You know the world means chessboard in the game), then follow the information collected by the horse, She can defeat her enemies easily.

But for the horse, it is really a dangerous and difficult work .So she must find a best path. Now we suppose every grid in the chessboard denotes a country, around which there is an octagon circumvallation with a certain thickness (show in graph). So if the horse wants to go to country 4 from I she should first break the country I' s wall then the country 4's, but actually he needn't break the whole wall, he just need to break wall D of the country I and wall H of the country 1. (if the horst want to go to country 2 from country I, he just need to break the wall B of country I and the wall F of the country 2).Of course,The horse needn't break any wall when he secondly tour on a same route,as the wall has been broken down.Breaking wall in enemy's country is really dangerous, so she should find a way which costs the least workload.

But you know, she is just a girl, as an excellent programmer, you are very willing to write a program to help her, eh?

Input

The input of this problem starts with a positive number N, followed by N input blocks. Each block consists a 8*8 positive integer matrix, which denotes the wall's thickness of the correspondent country.

Output

For each test case you should just output a single number perline, which is the minimum total wall thickness the horse should break during the tour. Note: the horse should visit every country AT LEAST once. Suppose the horse start from the up-left country.

Sample Input

1
2 1 1 1 1 1 1 1
1 1 1 3 2 1 1 1
1 4 1 4 1 1 1 1
1 5 1 1 3 1 1 1
1 1 6 1 1 1 1 1
1 1 2 1 1 1 1 1
1 1 1 1 2 1 1 1
1 1 1 1 1 1 1 2

Sample Output

150

Submit

Source: ZOJ Monthly, February 2004