Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

dp

implementation

*1400

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Find the Spruce

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHolidays 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.

Input

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$$$).

Output

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

Example

Input

4 2 3 .*. *** 2 3 .*. **. 4 5 .***. ***** ***** *.*.* 5 7 ..*.*.. .*****. ******* .*****. ..*.*..

Output

5 3 23 34

Note

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)$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2024 14:07:29 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|