假期很快就要到了。里克意识到是时候考虑购买一棵传统的云杉树了。但 Rick 不希望真正的树木受到伤害,因此他决定在由“*”和“.”组成的 $$$n \times m$$$ 矩阵中找到一些树木。
为了找到每个云杉,首先让我们定义矩阵中的云杉是什么。一组矩阵单元称为高度为 $$$k$$$ 且原点为点 $$$(x, y)$$$ 的云杉,如果:
- 集合中的所有单元格都包含“*”。
- 对于每个 $$$1 \le i \le k$$$,行号为 $$$x+i-1$$$ 且列号在 $$$[y - i + 1, y + i - 1]$$$ 范围内的所有单元格必须是该集合的一部分。所有其他单元格不能属于该集合。
正确和错误云杉树的示例:
现在 Rick 想知道他的 $$$n \times m$$$ 矩阵包含多少棵云杉。帮助瑞克解决这个问题。
输入
每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10$$$)。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 500$$$) - 矩阵大小。
每个测试用例的接下来 $$$n$$$ 行包含 $$$m$$$ 个字符 $$$c_{i, j}$$$ — 矩阵内容。保证 $$$c_{i, j}$$$ 是“.”。或“*”。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$500^2$$$ ($$$\sum n \cdot m \le 500^2$$$)。
输出
对于每个测试用例,打印单个整数 - 矩阵中云杉的总数。
示例
输入 #1
4 2 3 .*. *** 2 3 .*. **. 4 5 .***. ***** ***** *.*.* 5 7 ..*.*.. .*****. ******* .*****. ..*.*..
输出 #1
5 3 23 34
注意
在第一个测试用例中,第一棵高度为 $$$2$$$ 的云杉的原点为 $$$(1, 2)$$$,第二棵高度为 $$$1$$$ 的云杉的原点为 $$$(1, 2)$$$,第三棵高度为 $$$1$$$ 的云杉的原点为点 $$$(2, 1)$$$,第四棵高度为 $$$1$$$ 的云杉的原点为点 $$$(2, 1)$$$,第四棵云杉的高度为 $$$1$$$。高度为 $$$1$$$ 的云杉的原点为点 $$$(2, 2)$$$,高度为 $$$1$$$ 的第五颗云杉的原点为点 $$$(2, 3)$$$。
在第二个测试用例中,高度为 $$$1$$$ 的第一棵云杉的原点为 $$$(1, 2)$$$,高度为 $$$1$$$ 的第二棵云杉的原点为 $$$(2, 1)$$$,高度为 $$$1$$$ 的第三棵云杉的原点为 $$$(2, 2)$$$。