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