题目描述

同学们经常做的一个题目，给你一个NxM的矩阵，矩阵里面每个格子上都有一个数，要求从左上角(1,1)，走到右下角(N, M)，每一步只能往下或者往右走，让你求经过的路径上数的总和最小。小Q发现这个问题太简单了，根本难不倒广大的OIer们。于是，他开始别出心裁了。

小Q想着现在给你一个01矩阵(即里面每个格子上的数是0或者1)，仍旧让你从(1,1)走到(N,M)，每次只能往下面一个格子或者右边一个格子走。定义一条好路径是指从起点到终点只经过0的格子。但是现在由于1的格子太多，所以可能无法完成这个任务。

于是，小Q想出了修改操作，对于每个修改操作(x1,y1)(x2,y2)，表示把以(x1,y1)为左上角，以(x2,y2)为右下角的矩阵里面的每个格子里面的数进行反转，即0变成1，1变成0。

问题是:最少需要多少次操作，才能使得这个矩阵存在好路径。现在请你来计算。

Input

从文件inverse.in中输入数据。

输入的第一行是一个正整数T，表示矩阵的个数。

对于每个矩阵：

输入的第一行是2 个正整数 N 和 M，表示矩阵的行数和列数。

接下来输入N行，每行有 M 个数，都是 0 或者 1，用空格隔开。

Output

输出到文件inverse.out中。

输出T 个非负整数，每行一个数，表示最少需要的操作数，使得对应矩阵存在好路径。

Samples

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

1

1
5 5
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0

4

2
10 10
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 1 0 1 1
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1

1
1

Limitation

【数据范围】

对于所有数据：1<=T<=20，1<=N，M<=10^3

其中30%的数据，N,M<=3 无特殊性质

其中20%的数据，N,M<=12 保证每个矩阵最多只需要1次操作

其中50%的数据，T<=2，N,M<=10^3 无特殊性质