Second International Programming Contest
March 28, 2004, Blagoevgrad, Bulgaria

Problem H
Winnie-the-Pooh
One day Winnie-the-Pooh decided to go to his friend Piglet. As his custom he wanted to give a present to Piglet. Because he lived in the forest, Pooh decided to take as much acorns as he could on his way to Piglet. You are asked to help Pooh. Note that the forest is a square (M x M, 3 < M < 101). Pooh's house is the leftmost and uppermost cell, Piglet's house is the rightmost and bottom most cell. The number N means that there are N acorns in the cell, for N = 0, 1, 2, 3, 4. The path begins in cell (1, 1) and ends in cell (M, M). Pooh can go from one cell to another if they have a common side and must arrive at Piglet's house as soon as possible (i.e. visiting exact 2M-1 cells). 
Input
The first line of input contains a single number N - number of test. The next lines are tests. The first line of each test contains a single number M. Each of the next M lines contains M numbers - the number found on the j-th position on the i-th line represent a cell (i, j). 
Output
You should output a single number on a single line for each test - the maximum possible amount of acorns collected by Pooh and given to Piglet. 
Sample Input
2 
3 
0 1 1 
0 4 2 
1 1 1 
5 
1 1 1 1 1 
0 0 3 4 3 
0 1 2 0 1 
1 1 1 0 1 
2 4 0 4 0 
Sample Output
8 
15