Escape From Huarong Road

The Chibi Battle is perhaps the most famous battle in the history of China. Liu Bei and Sun Quan won the battle after using a series of wonderful stratagem. Now, they are going to catch the leader of their enemy Cao Cao.

In order to help Cao Cao to escape, the soldiers of Cao Cao have been divided into several parts, and Cao Cao is in one of these part. Now they are all in a rectangle area which can be divided into many squares of the equal size. Once the soldiers get out of this area, they escape successfully.

Because Liu Bei and Sun Quan don't know exactly which part Cao Cao is in, so they all Cao Cao's soldiers.

In this area, some squares are lawns that can be passed, while some squares are Marshes that can't be passed. Liu Bei and SunQuan decide to set fire on lawns to those squares can't be passed. Because some reasons, set fire on different squares needs different length of time. And they can only set fire on one square at the same time. Now, Cao Cao and all his soldiers are having rest and you can assume that they won't move. Liu Bei and SunQuan want to know how much time they need at least to set fire to make Cao Cao and all his soldiers can't escape any way when they want to move. Can you help them?

The first line in the input file is a single integer: T (1 ≤ T ≤ 10), representing the number of test cases. For each test case, in the first line there are two integers: r and c (1 ≤ r, c ≤ 30) - the height and length of the area. Then there are r lines, in each line there are c integers. The j-th integer in the i-th line is m_ij. Each of these integers describes a square: if t_ij is positive, then the square is a lawn and it needs m_ij unit of time to set fire on it; if m_ij is 0, it means some soldiers of Cao Cao are having rest in this square; if m_ij is -1, means the square can't be passed.

When Cao Cao and his soldiers move, they can only move to a square that share an edge with the square they are in just now. All positive integers in the input file are smaller or equal to 100.

For each test case, output a single integer, means the number of unit of time Liu Bei and Sun Quan need to set fire so that Cao Cao and his soldiers can't get escape.

It is guaranted that the answer is exists.

1
4 3
1 2 1
1 10 1
1 0 -1
1 1 1

6

2010 ACM-ICPC Multi-University Training Contest（18）——Host by TJU