Migrated from Lutece 2978 棋盘

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

verjun 给了你一个大小为 $n\times m$ 的棋盘，每一个格子可以放一枚黑棋或白棋，其中一些格子已经被提前放上了棋子，其余的格子暂时什么都没有。 verjun 喜欢某种特定类型的图案，他要求你把所有空着的格子放上黑棋或白棋的一种，并且最大化他喜欢的图案的数量。 verjun 喜欢的图案形如 $4$ 个连续的格子组成的 $2\times 2$ 正方形，且棋子的排布必须是如下两种之一：

     BW        WB     
     WB        BW

其中W代表白棋（切瓦语的"wakuda"），B代表黑棋（科西嘉方言的“biancu”）。 请求出在所有空格子上放置棋子后，棋盘最多可能存在的 verjun 喜欢的图案的数量。

其实本题可以输出具体摆放方案，不过这里不做要求，有兴趣的同学可以思考一下。

Input

本题包含多组数据。 第一行一个整数 $T(1\le T\le 10^4)$，代表数据组数。 每组数据的第一行两个整数 $n ,m(1\le n, m\le 100)$，代表棋盘的尺寸。 接下来 $n$ 行每行一个长度为 $m$ 的字符串，第 $i$ 行的第 $j$个字符代表第 $i$ 行第 $j$ 列的格子的放置情况。B代表该格子已经放有白棋，W代表该格子已经放有黑棋，? 代表未放置棋子的格子。 保证 $\sum nm\le 10^6$。

Output

对于每组数据，输出一个整数，代表题述图案出现次数的最大值。

Samples

3
2 2
??
??
3 3
BW?
W?B
?BW
3 3
BW?
W?W
?W?

1
1
4

Resources

2023 UESTC ICPC Training for Graph