DIISLAND - THE DESERT ISLAND

You have the map of a diamond shaped desert island of order n. Given the energy required to travel through each cell, find the minimum energy to travel from initial position to the final position as shown in the figure.

From each cell you can move to any cell which shares an edge with it. You cannot travel backwards (The length of the path you choose will be equal to n.)

Input

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of an integer n, the order of the diamond (n is always odd) followed by the description of the map.

Output

For each test case, find the minimum energy required to travel from initial position to the destination.

Constraints

1 <= t <= 100

1 <= n <= 200 and n is odd

1 <= map[i][j] <= 100

Example

Input:
3
5
1
2 3
6 5 4
9 10
3
5
1
2 1
2 2 1
2 1
1
1
5

Output:
20
5
5

Added by:cegprakash
Date:2014-11-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU

hide comments
2023-04-10 20:24:42 Simes
Almost identical to GO4DIMON
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.