题目描述

小民是浙江机电职业技术大学的学生，他非常喜欢他学校的英文缩写 ZIME。

现在给你一个大小为 $n×m$ 的矩阵，其中 $n$ 和 $m$ 都是偶数。矩阵的每个格子包含字母 Z I M E 其中之一。 小民将这个矩阵视为一个螺旋状结构，并从左上角按照顺时针方向遍历。他将矩阵分成多个层次，每一层都是环绕其外部的一个螺旋形路径。

例如尺寸为 $n×m$ 的矩阵的第一层定义为：长度为 $2×(n+m−2)$，宽度为 $1$，包含矩阵最外层的元素。每个后续层都定义为从原始矩阵中移除所有先前层后，剩余部分的第一层。

聪明的你能告诉小民，在所有层中，字符串 "ZIME" 出现的总次数吗？

输入格式

第一行包含一个整数 $t$ ($1≤t≤100$) 代表测试用例的数量。

每个测试用例的第一行包含一对数字 $n$ 和 $m$ ($2≤n,m≤10^3 , n,m$ 是偶数)。

接下来是 $n$ 行，长度为 $m$ ，包含字母 Z I M E 其中之一。 保证所有测试用例的 $n⋅m$ 的总和不超过 $10^6$ 。

输出格式

对于每个测试用例，输出一个数字，代表当前矩阵所有层中字符串 ZIME 出现的总次数。

3
2 4
ZIME
ZZZZ
2 2
IM
ZE
4 4
IMEZ
ZMEI
IIZM
ZIEM

1
1
2

解释 #1

第 $3$ 个示例中出现 ZIME。不同的层使用不同的颜色。