题目内容

在一个 $R$ 行 $C$ 列的矩形区域内，每个单元格被标记为 0、1 或 #。其中 # 表示阻塞格，其余为可操作格。 两个可操作格若在上下左右四个方向之一相邻，则称它们为一对「相邻格」。若一对相邻格的标记不同（一个为 0，另一个为 1），则称这对相邻格产生一个「异态边」。 定义整个区域的「异态指标」为：所有异态边的总数对 $2$ 取模的结果（即奇偶性）。

现在你可以进行一次操作：选择一个可操作格，将其标记取反（0 变为 1，1 变为 0）。请计算，有多少个可操作格在操作后，整个区域的异态指标保持不变。

约束：行数 $R$ 与列数 $C$ 均不小于 $1$，且 $R \times C \le 2 \times 10^6$。一个测试文件中所有测试数据的 $R \times C$ 总和也不超过 $2 \times 10^6$。测试数据组数 $T$ 不超过 $10^4$。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行包含两个整数 $R$ 和 $C$，表示行数和列数。 接下来 $R$ 行，每行是一个长度为 $C$、仅包含字符 0、1、# 的字符串，描述该行的标记情况。

输出描述

对于每组测试数据，输出一行一个整数，表示操作后异态指标不变的可操作格数量。

样例1

输入

1
1 3
010

输出

1

说明

网格大小为 $1 \times 3$，三个格子均为非墙格。

• 第 1 个格子为 0，其唯一的非墙邻居是中间的 1，邻居数 $d = 1$，为奇数，翻转后会改变异态指标的奇偶性。
• 第 2 个格子为 1，左右各有一个非墙邻居（0 和 0），邻居数 $d = 2$，为偶数，翻转后异态指标保持不变。
• 第 3 个格子为 0，唯一的非墙邻居是中间的 1，$d = 1$，奇数，不保持。 因此只有中间的格子满足条件，答案为 1。

样例2

输入

1
2 2
0#
#1

输出

2

说明

网格中有两个非墙格：左上角的 0 和右下角的 1。

• 左上角的 0：右边和下边均为墙 #，无非墙邻居，$d = 0$（偶数），翻转后异态指标不变。
• 右下角的 1：上边和左边均为墙，同样 $d = 0$，保持不变。 因此两个格子都满足条件，答案为 2。

样例3

输入

1
3 3
000
000
000

输出

5

说明

所有格子均为非墙格，且标记均为 0。当前异态指标为 $0$（偶数）。

• 四个角上的格子（$(1,1),(1,3),(3,1),(3,3)$）各有 $2$ 个非墙邻居，$d = 2$ 为偶数，翻转后产生 $2$ 条异态边，$2 \bmod 2 = 0$，奇偶性不变。
• 中心格子 $(2,2)$ 有 $4$ 个非墙邻居，$d = 4$ 为偶数，翻转后产生 $4$ 条异态边，模 $2$ 仍为 $0$，不变。
• 四条边上的非角格子（如 $(1,2),(2,1),(2,3),(3,2)$）各有 $3$ 个非墙邻居，$d = 3$ 为奇数，翻转后异态指标发生变化。 因此共有 $4 + 1 = 5$ 个格子满足条件，答案为 5。