题目描述

小民是浙江机电职业技术大学的学生，他非常喜欢他学校的英文缩写 '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≤1e3 , n,m 是偶数)。 接下来是 n 行，长度为 m ，包含字母 'Z'  'I'  'M'  'E' 其中之一。 保证所有测试用例的 n⋅m 的总和不超过 1e6 。

输出格式

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

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

1
1
2

提示

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