10644: 回家种田

Abandon毕业后准备回家种田了。他在家乡买了个N*M块的大农田并且全都种上了红薯(3<=N,M<=50)，现在准备用特殊的装置给田里浇水。每一个装置只能灌溉特殊的一个区域，并且装置必须放在某一块田上。假设用坐标(x,y)来表示这N*M块田地，则整个农田的四个边角坐标便分别是(1,1)\(n,1)\(1,m)\(n,m)。每一次操作Abandon都可以选择一个放置在某个坐标(x0,y0)的田上的装置（每个装置的位置给定且固定），再选择某个田地的边角(x1,y1)，然后该装置便可以灌溉所有(p,q)的田地，其中(min(x0, x1) ≤ p ≤ max(x0, x1), min(y0, y1) ≤ q ≤ max(y0, y1).)

像Abandon这种毕业只能回家种红薯的学渣当然不会算他最少需要几次才能把整个农田都浇上水，所以他跑来求助你们了。

HINT

如下图所示3*3的农田，其中(2,2)这块田（即农田正中央）有一个装置，则Abandon至少需要4步才能浇满整个农田：

多组数据。

首先一个正整数T表示数据组数

然后对于每一组数据，

第一行给定两个整数N，M(3<=N,M<=50)

接下来一个N*M的01矩阵，(i,j)为0表示这块田上没有灌溉装置，为1则表示有。数据保证至少有一个装置，并且不会出现在农田的四个角。

1
3 3
0 0 0
0 1 0
0 0 0

4