Problem 21257 --E:远古石门机关

21257: E:远古石门机关

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 9  Solved: 2
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][28kb]

Description

有一个远古石门,上面的机关是由n行m列格子组成。其中,凸起的格子是灰色的。每一次操作可以让其中一行或一列中凸起的格子全部按下。只有使用了最小次数的操作,石门才会打开,否则机关会复位。给定一个这样的机关,多少次操作才能打开石门呢?

Input

输入数据的第一行是一个整数T,表示有T组测试样例,接着是T行数据,每行两个整数n和m,分别表示机关格子的行数和列数。接着是个n行m列的矩阵,其中1表示格子是凸起的,0表示格子是按下的。T<=50,0<n,m<100。

Output

对于每组测试样例,输出打开石门的操作数并独占一行。

Sample Input

2
4 4
0000
0101
0000
0100
3 3
111
010
000

Sample Output

2
2

HINT

Source

[Submit][Status]