Bob is recently playing a game called Minecraft, especially a mod called Industrialcraft 2. The things you can do in this mod is to build machines. One of the basic machines is Miner.
The Automated Miner is the lazy man's answer to mining. Once you place the miner on the ground, then place a drill together with a scanner in the right position and provide enough electricity and mining pipes, the miner will automatically place mining pipes under it and mines all the ores in the scan range of the scanner.
Miner
However, Bob found that the miner's AI is limited, it follows the greedy strategy when mining, so there exists potential space for improvement to its electricity cost.
Mining is processed layer by layer. The range n*n is determined by the scanner you are using. It can be 5*5, 7*7 or 9*9. So the problem you are facing now is to design the best strategy which wastes the least electricity on useless stones.
A map of the current layer will be provided to you. It is of size n*n. A typical map of size 5*5 is shown below.
00111
00191
09vX1
09X2@
099@1
'v' shows the position of the drill, that block has already been mined. It is guaranteed 'v' is at the center of this square region, and there is only one 'v' in each map.
'0'-'9' in the map shows a stone which requires the digit amount of electricity. For example, '9' means there is a stone at that position which requires 9 units of electricity to be mined.
'@' shows a block with a precious ore.
'X' shows a block with an obstacle. Your drill is not powerful enough to mine this obstacle.
A block can be mined only after at least one of its adjacent blocks has already been mined. The block where the drill is in has already been mined. Two blocks are adjacent if they share an edge.
Your task is to tell the least units of electricity required to mine all the ores in a given map.
Note that, in Minecraft, ores are generated following specific rules. Generally, ore blocks appear together, they are generated as ore clusters.
@
@@@
@
The previous picture is a basic ore cluster, '*' can be any block.
@@
@@@@
@@
The previous picture shows two ore clusters stacking together.
Note that Uranium ore being extremely precious does not appear as ore clusters. They can appear in any shape. However, there will not be more than 3 Uranium ores in a single map.
Input
There are multiple cases. The first line contains one integer T which is the number of test cases.
For each case, the first line contains an integer n( 5 ≤ n ≤ 9, n is an odd number).
For the next n lines, each line contains n characters showing the map. Note that, the map will contain only complete ore clusters. There will not be more than 3 Uranium ores on the map.
Output
One integer for each test case indicating the least units of electricity required to mine all ores. In case, it is impossible to mine all the ores, just output -1 instead.
Sample Input
3
5
11111
X1111
XXv11
@X111
1X111
5
@100@
32@00
0@v@0
00@00
0000@
7
0@00000
@@@0000
0@03000
002v100
0005000
0000000
0000000
Sample Output
-1
1
1
