称一个 $2\times 2$ 的 $01$ 矩阵是好的，当且仅当它任意相邻的两个数都不同。即：

01        或      10
10                01

给定一个由 $01?$ 组成的矩阵，你需要将 $?$ 替换为 $0$ 或 $1$，问好的 $2\times 2$ 子矩阵最多有多少个。

多测。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行给出两个整数 $n,m$。

接下来 $n$ 行，每行一个长为 $m$ 的字符串，给出矩阵。

输出格式

$T$ 行，每行一个整数表示一次询问的答案。

样例

input

3
2 2
??
??
3 3
01?
1?0
?01
3 3
01?
1?1
?1?

output

1
1
4

数据范围

保证 $1\leq T\leq 10^4;1\leq n,m\leq 100; \sum nm\leq 10^6$。

共 $10$ 组数据。

在前 $4$ 组中，$T=1,n,m\leq 10$ 且这 $4$ 组数据有一定梯度。