Problem C

Three Pigs

Input: standard input

Output: standard output

Time Limit: 2 seconds

Memory Limit: 32 MB

One day three pigs decide to go to their friend - Patachok. As their custom they want to give a present to Patachok. Because they live in forest, three pigs decide to take as much acorns as they can on their way to Patachok. But a wicked wolf finds out the pigs' plan. So the wolf puts traps on the pigs' way. You are asked to help the pigs. Note that the forest is a square (MxM, 1<=M<=11). Pigs' house is the leftmost and uppermost cell, Patachok's house in the rightmost and bottom most cell. "0" means that there is nothing in the cell, "1" means that there is one acorn in the cell, "2" means that there is a trap in the cell. Pig can go from one cell to other if they have a common side. A pig can't "visit" the same cell twice. Path of different pigs can be different. Any path begins in cell (1, 1) and ends in cell (N, N).

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. The next M lines each 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 or "-1" (without the quote) if the wolf catch the pigs.
 
Sample Input
2
3
0 0 1
0 1 0
0 2 0
4
0 0 0 0
2 1 0 0
2 1 2 0
2 1 2 0

Sample Output

2
1

---

(The Decider Contest, Problem setter: Andreev Konstantin, Nazarov Denis)