1461_B. 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 × m matrix consisting of "*" and ".".

<image>

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 ≤ i ≤ 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:

<image>

Now Rick wants to know how many spruces his n × 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 ≤ t ≤ 10).

The first line of each test case contains two integers n and m (1 ≤ n, m ≤ 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 ⋅ m over all test cases does not exceed 500^2 (∑ n ⋅ m ≤ 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).
```python
for _ in range(int(input())):
    n,m = list(map(int,input().split()))
    arr = []
    c = 0
    for i in range(n):
        z = list(input())
        c+=z.count("*")
        arr.append(z)
    ans = []
    for i in range(n):
        ans.append([0]*m)
    for i in range(m):
        for g in range(n):
            if arr[g][i] == "*":
                ans[g][i] = 1
    for i in range(n-2,-1,-1):

        for g in range(m):
            if arr[i][g] == "*":
                if g != 0 and g != m-1:
                    if arr[i+1][g] == "*" and arr[i+1][g-1] == "*" and arr[i+1][g+1] == "*":

                        ans[i][g]+= min(min(g,m-g-1),min(ans[i+1][g],ans[i+1][g-1],ans[i+1][g+1]) )

    s = 0
    for i in range(n):
        for g in range(m):
            s+=ans[i][g]
    print(s)

```