题目描述

有一个 $H\times W$ 的网格，每个格子被涂成白色或黑色。记第 $i$ 行（从上往下，$1\le i\le H$）、第 $j$ 列（从左往右，$1\le j\le W$）的格子为格子 $(i,j)$。网格的状态由 $H$ 个长度为 $W$ 的字符串 $S_1,S_2,\dots,S_H$ 给出：若 $S_i$ 的第 $j$ 个字符为 . 则格子 $(i,j)$ 为白色；若为 # 则为黑色。

高桥先生 想把若干（可以为零）黑色格子重涂为白色，使得网格中不存在全部为黑色的 $2\times 2$ 子方格。更精确地说，他想满足下面的条件：

• 对任意整数对 $(i,j)$（$1\le i\le H-1$ 且 $1\le j\le W-1$），格子 $(i,j),(i,j+1),(i+1,j),(i+1,j+1)$ 中至少有一个是白色。

请你求出使得上述目标成立所需重涂为白色的最少黑色格子数。

给出 $T$ 个测试用例，请分别回答。

输入格式

• 第一行包含一个整数 $T$（$1\le t\le 100$）——测试用例数。随后是 $T$ 个测试用例。

• 每个测试用例先给出两个整数 $H$ 和 $W$，

• 随后 $H$ 行每行一个字符串 $S_i$ 描述网格第 $i$ 行。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案（所需重涂的最少格子数）。

样例输入

2
5 5
####.
##.##
#####
.####
##.#.
2 2
..
..

样例输出

3
0

说明

样例解释

• 对第一个测试用例，初始网格如题中所示。可以将例如图中标号的 $3$ 个黑格涂成白色，使得不再存在全黑的 $2\times2$ 子方格。无法通过涂 $2$ 个或更少的格子实现目标，因此输出 $3$。
• 对第二个测试用例，网格已经满足条件（没有全黑的 $2\times2$ 子方格），因此答案为 $0$。

数据范围

• $1\le T\le 100$。
• $2\le H\le 7$。
• $2\le W\le 7$。
• 每个 $S_i$ 是长度为 $W$ 的字符串，只包含 . 和 #。
• $T,H,W$ 为整数。