Greg 拥有一个 $m \times n$ 的“纯粹酷炫甜美灯泡”网格，他想把所有的灯泡都点亮。最初，有些灯泡是亮的，有些是灭的。Greg 可以通过向灯泡发射激光来切换它们的状态。当他向一个灯泡发射激光时，该灯泡的状态会在“亮”和“灭”之间切换。同时，它还会切换该灯泡正下方所有的灯泡，以及该灯泡正左方所有的灯泡。请问 Greg 最少需要发射多少次激光才能点亮所有的灯泡？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。每个测试用例的第一行包含两个空格分隔的整数 $m$ 和 $n$ ($1 \le m, n \le 400$)。接下来的 $m$ 行，每行包含一个长度为 $n$ 的由 $1$ 和 $0$ 组成的字符串。$1$ 表示灯泡处于开启状态，$0$ 表示灯泡处于关闭状态。

输出格式

对于每个测试用例，输出一行，包含 Greg 为点亮所有灯泡所需发射激光的最少次数。

样例

输入格式 1

2
3 4
0000
1110
1110
2 2
10
00

输出格式 1

1
2

说明

在第一个测试用例中，向右上角的灯泡发射激光可以点亮所有熄灭的灯泡，且不会改变任何已经点亮的灯泡的状态。

在第二个测试用例中，向左上角和右上角的灯泡发射激光即可完成任务。