CF1461B.Find the Spruce

Holidays are coming up really soon. Rick realized that it's time to think about buying a traditional spruce tree. But Rick doesn't want real trees to get hurt so he decided to find some in an $n \times m$ matrix consisting of "*" and ".".

To find every spruce first let's define what a spruce in the matrix is. A set of matrix cells is called a spruce of height $k$ with origin at point $(x, y)$ if:

• All cells in the set contain an "*".
• For each $1 \le i \le k$ all cells with the row number $x+i-1$ and columns in range $[y - i + 1, y + i - 1]$ must be a part of the set. All other cells cannot belong to the set.

Examples of correct and incorrect spruce trees:

Now Rick wants to know how many spruces his $n \times m$ matrix contains. Help Rick solve this problem.

假期马上就要到了。Rick 意识到是时候考虑购买一棵传统的云杉树了。但 Rick 不想伤害真正的树木，于是他决定在由 * 和 . 组成的一个 $n \times m$ 矩阵中寻找“云杉树”。

为了找出矩阵中所有的云杉树，我们首先定义什么是矩阵中的“云杉树”。若一个矩阵单元格集合满足以下条件，则称其为以点 $(x, y)$ 为原点、高度为 $k$ 的云杉树：

• 该集合中所有单元格均包含字符 *；
• 对每个 $1 \le i \le k$，所有行号为 $x+i-1$、列号在区间 $[y - i + 1,\, y + i - 1]$ 内的单元格都必须属于该集合；其余任何单元格均不能属于该集合。

正确与错误的云杉树示例：

现在 Rick 想知道他的 $n \times m$ 矩阵中总共包含多少棵云杉树。请帮助 Rick 解决这个问题。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$).

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 500$) — matrix size.

Next $n$ lines of each test case contain $m$ characters $c_{i, j}$ — matrix contents. It is guaranteed that $c_{i, j}$ is either a "." or an "*".

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $500^2$ ($\sum n \cdot m \le 500^2$).

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $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$）。

For each test case, print single integer — the total number of spruces in the matrix.

对于每个测试用例，输出一个整数——矩阵中云杉树的总数。

In the first test case the first spruce of height $2$ has its origin at point $(1, 2)$, the second spruce of height $1$ has its origin at point $(1, 2)$, the third spruce of height $1$ has its origin at point $(2, 1)$, the fourth spruce of height $1$ has its origin at point $(2, 2)$, the fifth spruce of height $1$ has its origin at point $(2, 3)$.

In the second test case the first spruce of height $1$ has its origin at point $(1, 2)$, the second spruce of height $1$ has its origin at point $(2, 1)$, the third spruce of height $1$ has its origin at point $(2, 2)$.

在第一个测试用例中，第一棵高度为 $2$ 的云杉起源于点 $(1, 2)$，第二棵高度为 $1$ 的云杉起源于点 $(1, 2)$，第三棵高度为 $1$ 的云杉起源于点 $(2, 1)$，第四棵高度为 $1$ 的云杉起源于点 $(2, 2)$，第五棵高度为 $1$ 的云杉起源于点 $(2, 3)$。

在第二个测试用例中，第一棵高度为 $1$ 的云杉起源于点 $(1, 2)$，第二棵高度为 $1$ 的云杉起源于点 $(2, 1)$，第三棵高度为 $1$ 的云杉起源于点 $(2, 2)$。