Once upon a time there was a diamond shaped forest full of diamonds.

A lonely traveler wants to collect maximum diamonds from the forest. He travels from the initial postion to the destination as shown in the figure. From each cell he can move to any cell which shares an edge with it. He cannot travel backwards. Find the number of diamonds collected by the wise traveler who has the map of the forest.

Input

The first line consists of an integer t, the number of test cases. Each test case 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 print the number of diamonds collected by the wise traveler.

Constraints

1 <= t <= 100

1 <= n <= 200 and n is odd

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

Example

Input:
2
5
1
2 3
6 5 4
9 10
3
5
19
85 90
15 21 3
5 26
16

Output:
22
172