GO4DIMON - GO FOR DIAMONDS

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

diamond


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 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 testcase print the no. of diamonds collected by the wise traveler.

Input Constraints:

1<=t<=100

1<=n<=200 and n is odd

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

Sample Input:

2

5

1

2 3

6 5 4

9 10

3

5

19

85 90

15 21 3

5 26

16

Sample Output:

22

172


Added by:cegprakash
Date:2013-02-24
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.