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.


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


-----Examples-----

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

Difficulty: MEDIUM
Tags: Dynamic programming

Implementation

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	b = []
	for i in range(n):
		a.append(input())
		b.append([0] * m)
	s = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if a[i][j] == '*':
				if i == n - 1:
					b[i][j] = 1
					s += 1
				elif j == 0 or j == m - 1:
					b[i][j] = 1
					s += 1
				else:
					x = b[i + 1][j - 1:j + 2]
					b[i][j] = min(x) + 1
					s += b[i][j]
	print(s)


def find(mat):
	count = 0
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if mat[i][j] == '.':
				mat[i][j] = 0
			elif j == 0 or j == m - 1 or i == n - 1:
				mat[i][j] = 1
			else:
				min_val = min(mat[i + 1][j - 1], mat[i + 1][j], mat[i + 1][j + 1])
				mat[i][j] = min_val + 1
			count += mat[i][j]
	return count
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(list(input().strip()))
	print(find(mat))


def spruce(arr, n, m):
	cnt = 0
	dp = [[0 for i in range(m)] for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if arr[i][j] == '*':
				if j != 0 and j != m - 1 and (i != n - 1):
					dp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])
				else:
					dp[i][j] = 1
			cnt += dp[i][j]
	return cnt
for i in range(int(input())):
	(a, b) = map(int, input().strip().split())
	blanck = []
	for i in range(a):
		string = input()
		blanck.append(string)
	print(spruce(blanck, a, b))


(n, m) = (0, 0)
matrix = list()
for t in range(int(input())):
	(n, m) = [int(num) for num in input().split()]
	matrix = list()
	for i in range(n):
		matrix.append([0 if char == '.' else 1 for char in input()])
	for i in range(n - 1, 0, -1):
		for j in range(1, m - 1):
			if matrix[i][j - 1] != 0 and matrix[i][j] != 0 and (matrix[i][j + 1] != 0) and (matrix[i - 1][j] != 0):
				matrix[i - 1][j] += min(matrix[i][j - 1], matrix[i][j], matrix[i][j + 1])
	count = 0
	for i in range(n):
		for j in range(m):
			count += matrix[i][j]
	print(count)


def readGenerator():
	while True:
		tokens = input().split(' ')
		for t in tokens:
			yield t
reader = readGenerator()

def readWord():
	return next(reader)

def readInt():
	return int(next(reader))

def readFloat():
	return float(next(reader))

def readLine():
	return input()

def solve(n, m, c):
	k = 0
	l = []
	r = []
	for rw in range(n):
		l.append([-1] * m)
		r.append([m] * m)
		for cl in range(m):
			if c[rw][cl] == '.':
				l[rw][cl] = cl
			elif cl > 0:
				l[rw][cl] = l[rw][cl - 1]
		for cl in reversed(range(m)):
			if c[rw][cl] == '.':
				r[rw][cl] = cl
			elif cl < m - 1:
				r[rw][cl] = r[rw][cl + 1]
	for rw in range(n):
		for cl in range(m):
			for i in range(rw, n):
				d = i - rw
				start = cl - d
				end = cl + d
				if start < 0 or end > m - 1:
					break
				if l[i][cl] >= start or r[i][cl] <= end:
					break
				k += 1
	return k
t = readInt()
for _ in range(t):
	(n, m) = [readInt() for _ in range(2)]
	c = []
	for i in range(n):
		c.append(readLine())
	print(solve(n, m, c))


I = input
for _ in [0] * int(I()):
	(n, m) = map(int, I().split())
	a = [I() for _ in [0] * n]
	b = [0] * 501
	r = 0
	for s in a[::-1]:
		b = (0, *((s[i] < '.') * (min(b[i:i + 3]) + 1) for i in range(m)), 0)
		r += sum(b)
	print(r)


tcs = int(input())
for tc in range(tcs):
	(m, n) = list(map(int, input().split()))
	mn = list()
	li = list()
	ans = 0
	for i in range(m):
		inp = input()
		mn.append('.' + inp + '.')
	mn.append('.' + '.' * n + '.')
	li = [[1 if i == '*' else 0 for i in mn[j]] for j in range(m + 1)]
	for i in range(m - 1, -1, -1):
		for j in range(1, n + 1):
			if li[i][j]:
				li[i][j] += min(li[i + 1][j + 1], li[i + 1][j - 1], li[i + 1][j])
				ans += li[i][j]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(lst, cnt, dp) = ([input() for i in range(n)], 0, [[0 for i in range(m)] for j in range(n)])
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if lst[i][j] == '*':
				dp[i][j] = 1 + (min(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1]) if not (i == n - 1 or j == 0 or j == m - 1) else 0)
				cnt += dp[i][j]
	print(cnt)


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		grid.append(input())
	counters = [[0 for i in range(m)] for j in range(n)]
	ans = 0
	for r in range(n - 1, -1, -1):
		for c in range(m):
			if grid[r][c] == '*':
				counters[r][c] = 1
				if r < n - 1 and c > 0 and (c < m - 1):
					counters[r][c] += min([counters[r + 1][c - 1], counters[r + 1][c], counters[r + 1][c + 1]])
				ans += counters[r][c]
	print(ans)


def solve():
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
	dp = []
	for i in range(n):
		dp.append([])
		for j in range(m):
			dp[i].append((1 if a[i][j] == '*' else 0) if j == 0 else dp[i][j - 1] + (1 if a[i][j] == '*' else 0))
	answer = 0
	for x in range(n):
		for y in range(m):
			if a[x][y] == '.':
				continue
			for level in range(min(n - x, m - y, y + 1)):
				if dp[x + level][y + level] - (0 if y - level - 1 < 0 else dp[x + level][y - level - 1]) != level * 2 + 1:
					break
				answer += 1
	print(answer)
tests = int(input())
while tests > 0:
	solve()
	tests = tests - 1


from pprint import pprint
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	mat = [0 for i in range(n)]
	dp = [[0] * m for i in range(n)]
	for i in range(n):
		mat[i] = list(input())
	for col in range(m):
		dp[n - 1][col] = 1 if mat[n - 1][col] == '*' else 0
	for i in range(n - 2, -1, -1):
		for j in range(m):
			if mat[i][j] == '*':
				a = dp[i + 1][j - 1] if j - 1 >= 0 else 0
				b = dp[i + 1][j]
				c = dp[i + 1][j + 1] if j + 1 < m else 0
				dp[i][j] = 1 + min(a, b, c)
	ans = 0
	for row in dp:
		ans += sum(row)
	print(ans)


for _ in range(int(input())):
	k = [int(x) for x in input().split()]
	a = []
	for i in range(k[0]):
		a.append(input())
	dp = []
	for i in range(k[0]):
		t = []
		for j in range(k[1]):
			t.append(0)
		dp.append(t)
	s = 0
	for i in range(k[1]):
		if a[-1][i] == '*':
			dp[-1][i] = 1
			s += 1
	for i in range(k[0] - 2, -1, -1):
		for j in range(0, k[1]):
			if a[i][j] == '*':
				if j == 0 or j == k[1] - 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
			s += dp[i][j]
	print(s)


t = int(input())
i = 1
while i <= t:
	[n, m] = list(map(int, input().split()))
	arr = []
	ans = []
	total = 0
	for j in range(n):
		arr.append(input())
		ans.append([0 for k in range(m)])
	for j in range(n - 1, -1, -1):
		for k in range(m - 1, -1, -1):
			if arr[j][k] == '*':
				total += 1
				ans[j][k] += 1
				start = k - 1
				end = k + 1
				if start >= 0 and end <= m - 1 and (j + 1 <= n - 1):
					mini = min(ans[j + 1][k - 1], ans[j + 1][k], ans[j + 1][k + 1])
					total += mini
					ans[j][k] += mini
	print(total)
	i += 1


def solve(mat, n, m):
	res = 0
	dp = [[1 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '.':
				dp[i][j] = 0
	for i in range(n - 2, -1, -1):
		for j in range(1, m - 1):
			if dp[i][j] == 0:
				continue
			minh = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
			dp[i][j] = 1 + minh
	for i in range(n):
		for j in range(m):
			res += dp[i][j]
	return res
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mat = []
	for _ in range(n):
		row = input()
		mat.append(row)
	print(solve(mat, n, m))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	res = 0
	pre = []
	for i in range(n):
		s = input()
		v = [0] * m
		if s[0] == '.':
			v[0] = 1
		else:
			res += 1
		for j in range(1, m):
			if s[j] == '*':
				res += 1
				v[j] = v[j - 1]
			else:
				v[j] = 1 + v[j - 1]
		l.append(s)
		pre.append(v)
	for i in range(n):
		for j in range(m):
			if l[i][j] != '.':
				x = j - 1
				y = j + 1
				c = i + 1
				while c < n and x >= 0 and (y < m):
					if x == 0:
						cur = pre[c][y]
					else:
						cur = pre[c][y] - pre[c][x - 1]
					if cur >= 1:
						break
					else:
						res += 1
						x -= 1
						y += 1
						c += 1
	print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	martix = [input() for i in range(n)]
	dp = [[0 for j in range(m)] for i in range(n)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if martix[i][j] == '*':
				if not (i == n - 1 or j == 0 or j == m - 1):
					dp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1])
				else:
					dp[i][j] = 1
				ans += dp[i][j]
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	mat = []
	ans = [[0 for i in range(k)] for j in range(n)]
	for i in range(n):
		temp = input()
		mat.append(temp)
	for i in range(k):
		if mat[n - 1][i] == '*':
			ans[n - 1][i] = 1
	for i in range(n - 2, -1, -1):
		if mat[i][0] == '*':
			ans[i][0] = 1
		if mat[i][k - 1] == '*':
			ans[i][k - 1] = 1
		for j in range(1, k - 1):
			if mat[i][j] == '*':
				h = 1 + min(ans[i + 1][j], ans[i + 1][j - 1], ans[i + 1][j + 1])
				ans[i][j] = h
	res = 0
	for i in range(n):
		for j in range(k):
			res += ans[i][j]
	print(res)


import logging
import sys
from inspect import currentframe
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
logging.basicConfig(level=logging.DEBUG)

def dbg(*args):
	id2names = {id(v): k for (k, v) in currentframe().f_back.f_locals.items()}
	logging.debug(', '.join((id2names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args)))

def solve():
	(n, m) = map(int, input().split())
	s = [input().rstrip() for _ in range(n)]
	dp = [[0] * m for _ in range(n)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if s[i][j] == '*':
				if i == n - 1 or j == 0 or j == m - 1:
					dp[i][j] = 1
					ans += 1
				else:
					dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
					ans += dp[i][j]
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	w = []
	for j in range(n):
		l = input()
		l = list(l)
		w.append(l)
	dp = []
	for j in range(n):
		dp.append([0])
		for k in range(m):
			if w[j][k] == '*':
				dp[-1].append(1 + dp[-1][-1])
			else:
				dp[-1].append(dp[-1][-1])
	cnt = 0
	for j in range(n):
		for k in range(m):
			if w[j][k] == '*':
				ht = 0
				while ht + j < n and k - ht >= 0 and (k + ht < m):
					if dp[j + ht][k + ht + 1] - dp[j + ht][k - ht] == 2 * ht + 1:
						ht += 1
					else:
						break
				cnt += ht
	print(cnt)


class Vertex:

	def __init__(self, ch, q=0):
		self.ch = ch
		self.h = q

	def set(self, q):
		self.h = q
for t in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [[Vertex(ch) for ch in input()] for _ in range(n)]
	count = 0
	for y in range(n - 1, -1, -1):
		for x in range(m):
			if arr[y][x].ch == '.':
				continue
			if x == 0 or x == m - 1 or y == n - 1:
				h = 1
			else:
				h = min([arr[y + 1][x - 1].h, arr[y + 1][x].h, arr[y + 1][x + 1].h]) + 1
			arr[y][x].set(h)
			count += h
	print(count)


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
I = sys.stdin.readline

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def valid(row, col, rows, cols, rcross, lcross):
	return rows[row] == 0 and cols[col] == 0 and (rcross[col + row] == 0) and (lcross[col - row] == 0)

def div(n):
	tmp = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				n = n // i
				cnt += 1
			tmp.append((i, cnt))
	if n > 1:
		tmp.append((n, 1))
	return tmp

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		flag = True
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				flag = False
				break
		return flag

def main():
	ans = ''
	for _ in range(ii()):
		(n, m) = mi()
		tmp = []
		for i in range(n):
			tmp.append(I().strip())
		arr = []
		for i in range(n):
			a = []
			for j in range(m):
				if tmp[i][j] == '*':
					a.append(1)
				else:
					a.append(0)
			arr.append(a)
		for i in range(n - 2, -1, -1):
			for j in range(m):
				if arr[i][j] == 1:
					if j > 0 and j < m - 1:
						x = arr[i + 1][j]
						y = arr[i + 1][j + 1]
						z = arr[i + 1][j - 1]
						if x > 0 and y > 0 and (z > 0):
							arr[i][j] = min(x, y, z) + 1
		cnt = 0
		for i in range(n):
			cnt += sum(arr[i])
		ans += str(cnt) + '\n'
	print(ans)
main()


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		arr = []
		for _ in range(n):
			arr.append(list(input()))
		dp = [[0 for _ in range(m + 2)] for _ in range(n + 1)]
		ans = 0
		for r in range(n - 1, -1, -1):
			for c in range(1, m + 1):
				if arr[r][c - 1] == '*':
					dp[r][c] = min([dp[r + 1][c], dp[r + 1][c - 1], dp[r + 1][c + 1]]) + 1
					ans += dp[r][c]
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def compute_spruce(grid, width, x, y):
	height = 1
	while True:
		if x + height >= len(grid):
			break
		if width[x + height][y] >= height + 1:
			height += 1
		else:
			break
	return height
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	grid = []
	for _ in range(n):
		grid.append(list(input()))
	width = [[0 for _ in range(m)] for _ in range(n)]
	left = [[0 for _ in range(m)] for _ in range(n)]
	right = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		for j in range(m - 1, -1, -1):
			if grid[i][j] == '*':
				if j == m - 1:
					right[i][j] = 1
				else:
					right[i][j] = 1 + right[i][j + 1]
	for i in range(n):
		for j in range(m):
			if grid[i][j] == '*':
				if j == 0:
					left[i][j] = 1
				else:
					left[i][j] = 1 + left[i][j - 1]
	for i in range(n):
		for j in range(m):
			width[i][j] = min(left[i][j], right[i][j])
	total = 0
	dp = [[0 for _ in range(m)] for _ in range(n)]
	for j in range(m):
		if grid[0][j] == '*':
			dp[0][j] = 1
	for i in range(1, n):
		for j in range(m):
			dp[i][j] = min(dp[i - 1][j], width[i][j] - 1) + 1
	for i in range(n):
		for j in range(m):
			total += dp[i][j]
	print(total)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
test_cases = 1
test_cases = int(input())
for _ in range(test_cases):
	(n, m) = map(int, input().split())
	a = [str(input()) for i in range(n)]
	l = [[0 for i in range(m)] for j in range(n)]
	r = [[0 for i in range(m)] for j in range(n)]
	for i in range(n):
		cnt = 0
		for j in range(m - 1, -1, -1):
			if a[i][j] == '*':
				cnt += 1
			else:
				cnt = 0
			r[i][j] = cnt
	for i in range(n):
		cnt = 0
		for j in range(m):
			if a[i][j] == '*':
				cnt += 1
			else:
				cnt = 0
			l[i][j] = cnt
	ans = 0
	for i in range(n):
		for j in range(m):
			k = i
			cnt = 1
			while k < n:
				if l[k][j] >= cnt and r[k][j] >= cnt:
					k += 1
					cnt += 1
				else:
					break
			ans += k - i
	print(ans)


import sys
input = sys.stdin.readline

def check(i, j, ls):
	global n, m, dp
	ans = 0
	for c in range(min(j + 1, n - i, m - j)):
		if dp[i + c][j + c] - dp[i + c][j - c] + (1 if ls[i + c][j - c] == '*' else 0) == 2 * (c + 1) - 1:
			ans += 1
		else:
			return ans
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		mat.append(input())
	dp = [[0 for i in range(m)] for _ in range(n)]
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '*':
				dp[i][j] = 1 if j == 0 else dp[i][j - 1] + 1
			else:
				dp[i][j] = dp[i][max(j - 1, 0)]
	ans = 0
	for row in range(n):
		for columb in range(m):
			if mat[row][columb] == '*':
				ans += check(row, columb, mat)
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	count = 0
	trees = dict()
	for i in range(n - 1, -1, -1):
		for j in range(0, m):
			if l[i][j] == '*':
				x = 0
				if i != n - 1 and j >= 1 and (j <= m - 2):
					if (i + 1, j - 1) in trees and (i + 1, j) in trees and ((i + 1, j + 1) in trees):
						x = min(trees[i + 1, j - 1], trees[i + 1, j], trees[i + 1, j + 1])
				count += x + 1
				trees[i, j] = 1 + x
	print(count)


def dfs(x, y):
	if sublist[x][y] > 0:
		return sublist[x][y]
	flag = 0
	if x + 1 < n and y - 1 > -1 and (y + 1 < m):
		if matrix[x + 1][y - 1:y + 2] == '***':
			flag = 1
	if flag:
		sublist[x][y] = 1 + min(dfs(x + 1, y), dfs(x + 1, y - 1), dfs(x + 1, y + 1))
		return sublist[x][y]
	else:
		sublist[x][y] = 1
		return sublist[x][y]
testcase = int(input())
for i in range(testcase):
	nm = list(map(int, input().split()))
	n = nm[0]
	m = nm[1]
	sublist = [[0 for i in range(m)] for y in range(n)]
	matrix = []
	count = 0
	for y in range(n):
		matrix.append(input())
	for a in range(n):
		for b in range(m):
			if matrix[a][b] == '*':
				count += dfs(a, b)
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = [[0 for j in range(m)] for i in range(n)]
	mat = [input() for i in range(n)]
	count = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if mat[i][j] == '*':
				if i == n - 1 or j == 0 or j == m - 1:
					ans[i][j] = 1
				else:
					ans[i][j] = 1 + min(ans[i + 1][j], ans[i + 1][j + 1], ans[i + 1][j - 1])
				count += ans[i][j]
	print(count)


from sys import stdin, stdout
for i in range(int(stdin.readline())):
	(n, m) = [int(x) for x in stdin.readline().split()]
	l = [[0] * m for j in range(0, n)]
	arr = [[0] * m for j in range(0, n)]
	for rows in range(0, n):
		l[rows] = list(stdin.readline())
	count = 0
	j = 1
	for r in range(0, n):
		for c in range(0, m):
			if l[r][c] == '.':
				continue
			else:
				arr[r][c] = j
				j += 1
	for r in range(0, n):
		for c in range(0, m):
			if l[r][c] == '*':
				count += 1
				for k in range(1, n - r):
					if c - k >= 0 and c + k < m:
						if arr[r + k][c + k] - arr[r + k][c - k] + 1 == 2 * k + 1:
							count += 1
						else:
							break
	stdout.write(str(count) + '\n')


import math
t = int(input())

def solve():
	(n, m) = list(map(int, input().split()))
	graph = []
	dp = [[0] * (m + 1)]
	for x in range(n):
		graph.append(list(input()))
		dp.append([0] * (m + 1))
	ans = 0
	for x in range(n):
		continuity = 0
		for y in range(m):
			if graph[x][y] == '*':
				continuity += 1
				dp[x + 1][y + 1] = min(dp[x][y] + 1, int((continuity - 1) / 2) + 1)
				ans += dp[x + 1][y + 1]
			else:
				continuity = 0
	return ans
for i in range(t):
	output = solve()
	print(output)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	table = [input() for _ in range(n)]
	dp = [[0 for _ in range(m)] for __ in range(n)]
	res = 0
	for i in range(n - 1, -1, -1):
		for j in range(0, m):
			if table[i][j] == '*':
				if i == n - 1 or j == 0 or j == m - 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
				res += dp[i][j]
	print(res)
	t -= 1


def main():
	import sys
	input = sys.stdin.readline
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		c = [input() for i in range(n)]
		C = [[0] * (m + 1) for i in range(n)]
		ans = 0
		for i in range(n):
			for j in range(m):
				if c[i][j] == '*':
					ans += 1
					C[i][j + 1] = C[i][j] + 1
		for i in range(n):
			for j in range(m):
				if c[i][j] == '*':
					for k in range(1, n - i):
						if j - k < 0 or j + k >= m:
							break
						elif C[i + k][j + k + 1] - C[i + k][j - k] == k * 2 + 1:
							ans += 1
						else:
							break
		print(ans)
main()


import io
import os
from collections import Counter, defaultdict, deque

def solve(R, C, grid):
	ans = 0
	dp = [[0 for c in range(C)] for r in range(R)]
	for r in reversed(range(R)):
		for c in range(C):
			if grid[r][c] == '*':
				count = max(dp[r][c], 1)
				if r < R - 1 and c > 0 and (c < C - 1):
					count = max(count, min(dp[r + 1][c - 1], dp[r + 1][c], dp[r + 1][c + 1]) + 1)
				dp[r][c] = count
				ans += count
	if False:
		print()
		for row in dp:
			print('\t'.join(map(str, row)))
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, M) = [int(x) for x in input().split()]
	grid = [list(input().decode().rstrip()) for i in range(N)]
	ans = solve(N, M, grid)
	print(ans)


T = int(input())
for t in range(T):
	(N, M) = list(map(int, input().split()))
	a = [list(input()) for n in range(N)]
	ans = 0
	for i in range(N):
		for j in range(M):
			if a[i][j] == '*':
				a[i][j] = 1
			elif a[i][j] == '.':
				a[i][j] = 0
	for i in range(N - 2, -1, -1):
		for j in range(1, M - 1):
			if a[i][j] != 0:
				a[i][j] = min(a[i + 1][j - 1], a[i + 1][j], a[i + 1][j + 1]) + 1
	for i in range(N):
		for j in range(M):
			ans += a[i][j]
	print(ans)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	res = 0
	m = [[0 for i in range(c + 2)] for j in range(r + 1)]
	data = [0 for i in range(r)]
	for row in range(r):
		data[row] = input()
	for i in range(row, -1, -1):
		for j in range(c):
			if data[i][j] == '*':
				m[i][j + 1] = min(m[i + 1][j], m[i + 1][j + 1], m[i + 1][j + 2]) + 1
	print(sum([sum(i) for i in m]))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	inp = []
	out = 0
	for i in range(n):
		inp.append(list(input()))
	mat = [[] for i in range(n)]
	for i in range(n):
		for j in range(m):
			k = 0
			while j - k >= 0 and j + k < m:
				if inp[i][j - k] == '*' and inp[i][j + k] == '*':
					k += 1
				else:
					break
			mat[i].append(k)
	for i in range(n):
		for j in range(m):
			k = 0
			while i + k < n:
				if mat[i + k][j] >= k + 1:
					k += 1
				else:
					break
			out += k
	print(out)


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)


import sys, io, os, time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect, math, heapq
alphabet = 'abcdefghijklmnopqrstuvwxyz'
input = sys.stdin.readline
for ii in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(map(str, input()))[:-1])
	rowsum = []
	ans = 0
	colsum = [[0] * (m + 1) for i in range(n + 1)]
	for i in range(n):
		for j in range(m):
			if arr[i][j] == '*':
				colsum[i][j + 1] = colsum[i][j] + 1
				ans += 1
			else:
				colsum[i][j + 1] = colsum[i][j]
	for i in range(n):
		for j in range(m):
			temp = 0
			if arr[i][j] == '*':
				off = 1
				for x in range(i + off, n):
					if i + off < n + 1 and j + off + 1 < m + 1 and (j - off >= 0) and (colsum[i + off][j + off + 1] - colsum[i + off][j - off] == 2 * off + 1):
						off += 1
						temp += 1
					else:
						break
			ans += temp
	print(ans)


from collections import defaultdict, deque
import sys
import bisect
input = sys.stdin.readline
mod = 1000000007
t = int(input())
for ii in range(t):
	(n, m) = map(int, input().split())
	MAP = [[i for i in input() if i != '\n'] for i in range(n)]
	count = 0
	for i in range(n):
		for j in range(m):
			if MAP[i][j] == '*':
				count += 1
	COUNT0 = [[0] * m for i in range(n)]
	COUNT1 = [[0] * m for i in range(n)]
	for i in range(1, n):
		for j in range(1, m):
			if MAP[i][j] == MAP[i][j - 1] == MAP[i - 1][j] == '*':
				COUNT0[i][j] = min(COUNT0[i][j - 1], COUNT0[i - 1][j]) + 1
	for i in range(1, n):
		for j in range(m - 2, -1, -1):
			if MAP[i][j] == MAP[i][j + 1] == MAP[i - 1][j] == '*':
				COUNT1[i][j] = min(COUNT1[i][j + 1], COUNT1[i - 1][j]) + 1
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += min(COUNT0[i][j], COUNT1[i][j])
	print(ans + count)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from math import inf
for _ in range(ii1()):
	(n, m) = iia()
	arr = []
	for i in range(n):
		arr.append(is1())
	ans = 0
	dp = [[0] * m for _ in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if arr[i][j] == '*':
				if i == n - 1 or j == 0 or j == m - 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])
			ans += dp[i][j]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [list(input()) for i in range(n)]
	dp = [[0] * (m + 2) for i in range(n + 1)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(1, m + 1):
			if arr[i][j - 1] == '*':
				dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
			ans += dp[i][j]
	print(ans)


t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		tmp = input()
		a.append(tmp)
	sum = []
	kq = []
	ans = int(0)
	for i in range(n):
		tmp = []
		tmp1 = []
		for j in range(m):
			tmp.append(int(0))
			tmp1.append(int(0))
		sum.append(tmp)
		kq.append(tmp1)
	for i in range(n):
		if a[i][0] == '*':
			sum[i][0] = 1
		else:
			sum[i][0] = 0
	for i in range(n):
		for j in range(1, m):
			if a[i][j] == '.':
				sum[i][j] = 0
			else:
				sum[i][j] = sum[i][j - 1] + 1
	for i in range(n):
		for j in range(m):
			if n == 0 or m == 0:
				kq[i][j] = sum[i][j]
				ans = ans + sum[i][j]
			else:
				if sum[i][j] != 0:
					kq[i][j] = min(kq[i - 1][j - 1] + 1, (sum[i][j] - 1) // 2 + 1)
				else:
					kq[i][j] = 0
				ans = ans + kq[i][j]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for __ in range(n):
		a.append(input())
	dp = [[1 if c == '*' else 0 for c in r] for r in a]
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if dp[i][j] == 1 and i < n - 1 and (0 < j < m - 1):
				dp[i][j] += min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
	print(sum((sum(d) for d in dp)))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ma = [input() for i in range(n)]
	dp = [[0 for j in range(m)] for i in range(n)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if ma[i][j] == '*':
				if i != n - 1 and j != 0 and (j != m - 1):
					dp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1])
				else:
					dp[i][j] = 1
				ans += dp[i][j]
	print(ans)


from sys import stdin
input = stdin.readline

def find(i, j):
	mi = 1000000.0
	for h in range(2):
		if j - h < 0 or j + h >= m:
			mi = 0
			break
		mi = min(mi, processed[i + 1][j - h], processed[i + 1][j + h])
	processed[i][j] = mi + 1

def func():
	ans = 0
	for i in range(n):
		for j in range(m):
			if grid[i][j] == '*':
				processed[i][j] = 1
	for i in range(n - 2, -1, -1):
		for j in range(m - 1, -1, -1):
			if grid[i][j] == '*':
				find(i, j)
	for i in range(n):
		for j in range(m):
			ans += processed[i][j]
	print(ans)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = [list(input()) for __ in range(n)]
	processed = [[0 for x in range(m)] for y in range(n)]
	func()


def result(arr, n, board_number, m):
	sum = 0
	for j in range(m):
		if arr[n - 1][j] == '*':
			board_number[n - 1][j] = 1
		else:
			board_number[n - 1][j] = 0
		sum += board_number[n - 1][j]
	for i in range(n - 2, -1, -1):
		for j in range(m):
			if arr[i][j] == '.':
				board_number[i][j] = 0
			elif j == 0 or j == m - 1:
				if arr[i][j] == '*':
					board_number[i][j] = 1
				else:
					board_number[i][j] = 0
			else:
				board_number[i][j] = 1 + min(board_number[i + 1][j], board_number[i + 1][j + 1], board_number[i + 1][j - 1])
			sum += board_number[i][j]
	return sum
no_tests = int(input())
res = []
for i in range(no_tests):
	arr = []
	board_number = []
	dimension = input().split()
	(n, m) = (int(dimension[0]), int(dimension[1]))
	for row in range(n):
		read_arr = input()
		tmp = []
		tmp_board = []
		for col in range(m):
			tmp.append(read_arr[col])
			tmp_board.append(0)
		arr.append(tmp)
		board_number.append(tmp_board)
	res.append(result(arr, n, board_number, m))
for each in res:
	print(each)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
	count = 0
	dp = []
	for i in range(n):
		dp.append([])
		for j in range(m):
			dp[i].append((0 if a[i][j] == '.' else 1) if j == 0 else dp[i][j - 1] + (0 if a[i][j] == '.' else 1))
	for i in range(n):
		for j in range(m):
			if a[i][j] == '*':
				for k in range(min(n - i, m - j, j + 1)):
					if dp[i + k][j + k] - (0 if j - k - 1 < 0 else dp[i + k][j - k - 1]) == k * 2 + 1:
						count += 1
					else:
						break
	print(count)


t = int(input())
for _ in range(t):
	(m, n) = [int(i) for i in input().split()]
	matrix = []
	for _ in range(m):
		matrix.append(input())
	count = [[0 for _ in range(n)] for _ in range(m)]
	res = 0
	for i in range(m):
		start = 0
		for j in range(n):
			if matrix[i][j] == '*':
				continue
			else:
				while start < j:
					L = j - start
					if L == 1:
						count[i][start] = 1
						res += 1
					elif i > 0 and count[i - 1][start + 1] >= L - 2:
						count[i][start] = L
						res += (L + 1) // 2
					elif i == 0:
						count[i][start] = 1
						res += 1
					else:
						L = count[i - 1][start + 1] + 2
						count[i][start] = L
						res += (L + 1) // 2
					start += 1
				start += 1
		else:
			while start < n:
				L = n - start
				if L == 1:
					count[i][start] = 1
					res += 1
				elif i > 0 and count[i - 1][start + 1] >= L - 2:
					count[i][start] = L
					res += (L + 1) // 2
				elif i == 0:
					count[i][start] = 1
					res += 1
				else:
					L = count[i - 1][start + 1] + 2
					count[i][start] = L
					res += (L + 1) // 2
				start += 1
	print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = [list(input()) for _ in range(n)]
	dp = [[0] * m for _ in range(n)]
	ans = 0
	s = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if matrix[i][j] == '*':
				dp[i][j] = 1
				if i + 1 < n and j - 1 >= 0 and (j + 1 < m):
					dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1
			s += dp[i][j]
	print(s)


from functools import lru_cache
import sys
sys.setrecursionlimit(250000)
input = sys.stdin.readline
t = int(input())
for _ in range(t):

	@lru_cache(None)
	def dfs(h, w):
		if h < n - 1 and 0 < w < m - 1 and (tree[h + 1][w - 1] == '*') and (tree[h + 1][w] == '*') and (tree[h + 1][w + 1] == '*'):
			return min(dfs(h + 1, w - 1), dfs(h + 1, w), dfs(h + 1, w + 1)) + 1
		else:
			return 1
	(n, m) = map(int, input().split())
	tree = [list(input()) for i in range(n)]
	ans = 0
	for i in range(n):
		for j in range(m):
			if tree[i][j] == '*':
				ans += dfs(i, j)
	print(ans)


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
for _ in range(t()):
	(n, m) = ll()
	a = []
	ans = [0]
	d = []
	for i in range(n):
		s = ss()
		a.append(s)
		d.append([0] * m)
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if a[i][j] == '*':
				d[i][j] += 1
				if j - 2 >= 0 and i - 1 >= 0 and (j >= 2):
					if a[i][j - 1] == a[i][j - 2] == '*' and a[i - 1][j - 1] == '*':
						d[i - 1][j - 1] = min(d[i][j - 1], d[i][j], d[i][j - 2])
	for i in range(n):
		ans[0] += sum(d[i])
	print(ans[0])


import sys
import math, cmath
import bisect
from functools import reduce, lru_cache
from collections import Counter
from itertools import groupby

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def input():
	return sys.stdin.readline().rstrip()

def index(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	return False

def create_pref(arr):
	pref = [0] * len(arr)
	pref[0] = arr[0]
	for i in range(1, len(arr)):
		pref[i] += pref[i - 1] + arr[i]
	return pref

def modpow(x, n, m):
	if n == 0:
		return 1 % m
	u = modpow(x, n // 2, m)
	u = u * u % m
	if n % 2 == 1:
		u = u * x % m
	return u
for _ in range(getN()):
	(n, m) = getNM()
	table = []
	for i in range(n):
		s = input()
		table.append([1 if x == '*' else 0 for x in s])
	table_pref = [create_pref(table[i]) for i in range(n)]
	ans = 0
	for i in range(n):
		for j in range(m):
			if table[i][j] == 1:
				s = 1
				for k in range(1, m):
					if i + k >= n or j - k < 0 or j + k >= m:
						break
					if table_pref[i + k][j + k] - (table_pref[i + k][j - k - 1] if j - k != 0 else 0) == (k + 1) * 2 - 1:
						s += 1
					else:
						break
				ans += s
	print(ans)


from sys import stdin
import sys
tt = int(stdin.readline())
for loop in range(tt):
	(n, m) = map(int, stdin.readline().split())
	a = []
	for i in range(n):
		a.append(stdin.readline()[:-1])
	dp = [[0] * m for i in range(n)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if a[i][j] == '*':
				if i == n - 1 or j == 0 or j == m - 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])
			ans += dp[i][j]
	print(ans)


def main():

	def conv(ind):
		if ind == '.':
			return 0
		else:
			return 1

	def check(x, y):
		tx = x
		ty = y
		height = 0
		count = 0
		broke = False
		while broke == False:
			if ty - height >= 0 and ty + height <= m - 1 and (tx + height <= n - 1):
				if ty - height == 0:
					num1 = 0
				else:
					num1 = dict1[tx + height][ty - height - 1]
				if dict1[tx + height][ty + height] - num1 == 1 + 2 * height:
					count += 1
					height += 1
				else:
					broke = True
					break
			else:
				broke = True
				break
		return count
	for j in range(int(input())):
		(n, m) = map(int, input().split())
		matr = []
		ans = 0
		dict1 = {}
		for s in range(n):
			row = [conv(k) for k in input()]
			matr.append(row)
		for s in range(n):
			pref = [matr[s][0]]
			for i in range(1, m):
				pref.append(pref[-1] + matr[s][i])
			dict1[s] = pref
		for s in range(n):
			for i in range(m):
				ans += check(s, i)
		print(ans)
main()


for t in range(int(input())):
	(r, c) = map(int, input().split())
	a = []
	for i in range(r):
		str = input()
		a.append(str)
	front = [[0 for i in range(c)] for j in range(r)]
	back = [[0 for i in range(c)] for j in range(r)]
	count = 0
	for i in range(r):
		count = 0
		for j in range(c):
			if a[i][j] == '*':
				count += 1
				front[i][j] = count
			else:
				count = 0
				front[i][j] = count
	for i in range(r):
		count = 0
		for j in range(c - 1, -1, -1):
			if a[i][j] == '*':
				count += 1
				back[i][j] = count
			else:
				count = 0
				back[i][j] = count
	add = 0
	k = 0
	count = 0
	for i in range(r):
		for j in range(c):
			k = i
			count = 1
			while k < r:
				if front[k][j] >= count and back[k][j] >= count:
					add += 1
					k += 1
					count += 1
				else:
					break
	print(add)


I = input
for _ in [0] * int(I()):
	a = [I() for _ in [0] * int(I().split()[0])]
	b = [0] * 501
	r = 0
	for s in a[::-1]:
		b = (0, *(x < '.' and min(b[i:i + 3]) + 1 for (i, x) in enumerate(s)), 0)
		r += sum(b)
	print(r)


a = int(input())
for o in range(a):
	(n, m) = map(int, input().split())
	pic = [0] * n
	for i in range(n):
		pic[i] = [0] * m
	for i in range(n):
		c = str(input())
		for j in range(m):
			pic[i][j] = c[j]
	new = [[0] * (m + 2) for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if pic[i][j] == '*':
				new[i][j + 1] = min(new[i + 1][j], new[i + 1][j + 1], new[i + 1][j + 2]) + 1
	k = 0
	for i in range(n + 1):
		for j in range(m + 2):
			k += new[i][j]
	print(k)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dict = []
	k = 0
	for i in range(n):
		dict.append(i)
		dict[i] = []
		a = list(input())
		for j in range(m):
			if a[j] == '*':
				k = k + 1
				dict[i].append(k)
			else:
				dict[i].append(0)
	for i in range(0, n - 1):
		for j in range(1, m - 1):
			p = dict[i][j]
			if dict[i][j] != 0:
				x = i + 1
				a = 1
				b = 2
				while x < n and j + a < m:
					if dict[x][j + a] - dict[x][j - a] == b:
						k = k + 1
						x = x + 1
						a = a + 1
						b = b + 2
					else:
						break
	print(k)


n = int(input())
for i in range(n):
	(p, q) = [int(x) for x in input().split()]
	tree = []
	for j in range(p):
		tree.append([1 if x == '*' else 0 for x in list(input())])
	for x in range(p - 2, -1, -1):
		for y in range(q):
			if x + 1 < p and y - 1 < q and (y + 1 < q) and (x + 1 >= 0) and (y - 1 >= 0) and (y + 1 >= 0):
				tree[x][y] = tree[x][y] + tree[x][y] * min(tree[x + 1][y - 1], tree[x + 1][y], tree[x + 1][y + 1])
	print(sum(map(sum, tree)))


T = int(input())
for t in range(T):
	(n, m) = list(map(int, input().split()))
	matrix = []
	ans = []
	for i in range(n):
		matrix.append(list(input()))
		ans.append([0] * m)
	for i in range(n):
		for j in range(m):
			if matrix[i][j] == '*':
				ans[i][j] = 1
	for i in range(n - 2, -1, -1):
		for j in range(1, m - 1):
			if matrix[i][j] == '*':
				ans[i][j] = min(ans[i + 1][j], ans[i + 1][j - 1], ans[i + 1][j + 1]) + 1
	mainans = 0
	for i in range(n):
		for j in range(m):
			mainans += ans[i][j]
	print(mainans)


import sys
t = int(input())
for test in range(t):
	[n, m] = list(map(int, input().split(' ')))
	a = []
	for i in range(n):
		a.append(input())
	res = 0
	b = []
	for i in range(n):
		k = 0
		bi = []
		for j in range(m):
			if a[i][j] == '*':
				bi.append(1)
				k += 1
				for x in range(1, (k + 1) // 2):
					bi[j - x] += 1
			else:
				bi.append(0)
				k = 0
		b.append(bi)
	for j in range(m):
		if b[0][j] > 0:
			res += 1
	for i in range(1, n):
		for j in range(m):
			res = res + min(b[i][j], b[i - 1][j] + 1, i + 1)
			b[i][j] = min(b[i][j], b[i - 1][j] + 1, i + 1)
	print(res)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		a = input()
		s = [0] * m
		for i in range(len(a)):
			if a[i] == '*':
				s[i] = 1
		l.append(s)
	for i in range(n):
		l[i].insert(0, 0)
	for i in range(n):
		for j in range(1, m + 1):
			if l[i][j]:
				l[i][j] += l[i][j - 1]
	star = 0
	for i in range(n):
		for j in range(1, m + 1):
			c = 0
			for k in range(0, n):
				if j + k < m + 1 and j - k > 0 and (i + k < n) and (l[i + k][j + k] - l[i + k][j - k - 1] == 2 * k + 1):
					c += 1
				else:
					break
			star += c
	print(star)


t = int(input())
for q in range(t):
	(n, m) = map(int, input().split())
	a = n * [0]
	for w in range(n):
		a[w] = input()
	dp = [[0 for i in range(m)] for j in range(n)]
	for i in list(reversed(range(n))):
		for j in range(m):
			if a[i][j] == '.':
				dp[i][j] = 0
			elif j > 0 and j < m - 1 and (i < n - 1):
				dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
			else:
				dp[i][j] = 1
	s = 0
	for i in dp:
		s += sum(i)
	print(s)


def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		mm = []
		ans = 0
		for i in range(n):
			s = input()
			l = []
			for j in s:
				if j == '.':
					l.append(0)
				else:
					l.append(1)
			mm.append(l)
		for i in range(n - 1, -1, -1):
			if i - 1 >= 0:
				for j in range(1, m - 1):
					if mm[i][j] > 0 and mm[i - 1][j] > 0:
						if mm[i][j - 1] > 0 and mm[i][j + 1] > 0:
							mm[i - 1][j] += min(mm[i][j - 1], mm[i][j + 1])
		ans = 0
		for l in mm:
			ans += sum(l)
		print(ans)
main()


from collections import deque
from pprint import pprint
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	q = deque()
	mat = [0 for i in range(n)]
	v = [[0] * m for i in range(n)]
	for i in range(n):
		mat[i] = list(input())
	first = False
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '.':
				q.append((i, j, 0))
				first = first or i == 0
				v[i][j] = 1
				mat[i][j] = 0
	if len(q) == 0 or not first:
		q.append((0, 0, 1))
		v[0][0] = 1
		mat[0][0] = 1
	while q:
		(r, c, dist) = q.popleft()
		for (row, col) in [(r + 1, c), (r, c - 1), (r, c + 1)]:
			if 0 <= row < n and 0 <= col < m:
				if not v[row][col]:
					mat[row][col] = min(col + 1, row + 1, m - col, dist + 1)
					q.append((row, col, dist + 1))
					v[row][col] = 1
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += mat[i][j]
	print(ans)


def solve():
	(n, m) = map(int, input().split())
	a = []
	dp = []
	for i in range(n):
		a.append([''] * m)
		dp.append([0] * m)
	for i in range(n):
		s = input()
		for j in range(m):
			a[n - i - 1][j] = s[j]
	for i in range(m):
		if a[0][i] == '*':
			dp[0][i] = 1
		else:
			dp[0][i] = 0
	for i in range(1, n):
		for j in range(m):
			if a[i][j] == '*':
				dp[i][j] = 1
				if j > 0 and j < m - 1:
					dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])
			else:
				dp[i][j] = 0
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += dp[i][j]
	print(ans)
tests = int(input())
while tests > 0:
	solve()
	tests = tests - 1


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

def f(x):
	fi = bisect_right(a, x)
	b = n - fi
	for i in range(q):
		if k[i] > 0:
			if k[i] > x:
				b += 1
			else:
				fi += 1
		elif -k[i] <= fi:
			fi -= 1
		else:
			b -= 1
	return fi > 0
t = N()
for i in range(t):
	(n, m) = RL()
	a = []
	for i in range(n):
		a.append(input())
	ans = 0
	b = [[0] for i in range(n)]
	for i in range(n):
		for j in range(m):
			if a[i][j] == '*':
				b[i].append(b[i][-1] + 1)
			else:
				b[i].append(b[i][-1])
	for i in range(n):
		for j in range(m):
			if a[i][j] == '*':
				tmp = 1
				w = 1
				ci = i
				while i < n - 1 and j + w < m and (j - w >= 0):
					if b[i + 1][j + w + 1] - b[i + 1][j - w] == w * 2 + 1:
						tmp += 1
						i += 1
						w += 1
					else:
						break
				i = ci
				ans += tmp
	print(ans)


for _ in range(int(input())):
	(ROW, COL) = map(int, input().split())
	arr = []
	for _ in range(ROW):
		arr.append(list(input()))
	sol = [[0 for i in range(COL)] for j in range(ROW)]
	for row in range(ROW):
		for col in range(COL):
			if arr[row][col] == '*':
				sol[row][col] = 1
	for row in range(ROW - 2, -1, -1):
		for col in range(COL):
			if col == 0 or col == COL - 1:
				pass
			elif sol[row][col] >= 1:
				sol[row][col] += min(sol[row + 1][col - 1], sol[row + 1][col], sol[row + 1][col + 1])
	x = 0
	for i in sol:
		x += sum(i)
	print(x)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	mt = []
	for i in range(n):
		mt.append(input())
	vst = []
	for i in range(n):
		vst.append([0 for j in range(m)])

	def fun(x, y):
		if mt[x][y] == '.':
			return 0
		elif not vst[x][y] == 0:
			return vst[x][y]
		elif x == n - 1 or y == m - 1 or y == 0:
			vst[x][y] = 1
			return 1
		else:
			op = min(fun(x + 1, y), fun(x + 1, y - 1), fun(x + 1, y + 1))
			if op == 0:
				vst[x][y] = 1
			else:
				vst[x][y] = op + 1
			return vst[x][y]
	sm = 0
	for i in range(n):
		for j in range(m):
			sm += fun(i, j)
	print(sm)


for y in range(int(input())):
	(n, m) = map(int, input().split())
	dp = []
	lst = []
	for i in range(n):
		dp.append([0] * m)
		lst.append(list(input()))
	cnt = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if lst[i][j] == '*':
				if i == n - 1 or j == 0 or j == m - 1:
					dp[i][j] = 0
				elif lst[i + 1][j - 1] == '*' and lst[i + 1][j] == '*' and (lst[i + 1][j + 1] == '*'):
					dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1]) + 1
				else:
					dp[i][j] = 0
				cnt += 1 + dp[i][j]
			else:
				pass
	print(cnt)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = []
	kiri = [[0 for i in range(m)] for j in range(n)]
	kanan = [[0 for i in range(m)] for j in range(n)]
	for i in range(n):
		s.append(list(map(lambda x: x == '*', input())))
	for i in range(n):
		for j in range(m):
			if j == 0:
				kiri[i][j] = 1
				if not s[i][j]:
					kiri[i][j] = 0
				continue
			if not s[i][j]:
				kiri[i][j] = 0
			else:
				kiri[i][j] = kiri[i][j - 1] + 1
		for j in range(m - 1, -1, -1):
			if j == m - 1:
				kanan[i][j] = 1
				if not s[i][j]:
					kanan[i][j] = 0
				continue
			if not s[i][j]:
				kanan[i][j] = 0
			else:
				kanan[i][j] = kanan[i][j + 1] + 1
	ans = 0
	for i in range(n):
		for j in range(m):
			if s[i][j]:
				temp = 1
				for k in range(i + 1, n):
					if kiri[k][j] - 1 >= k - i and kanan[k][j] - 1 >= k - i:
						temp += 1
					else:
						break
				ans += temp
	print(ans)


def solve_2(grid):
	n = len(grid)
	m = len(grid[0])
	count = 0
	dp = [[0 for x in range(m)] for y in range(n)]
	for i in range(m):
		if grid[n - 1][i] == '*':
			dp[n - 1][i] = 1
	for j in range(n):
		if grid[j][m - 1] == '*':
			dp[j][m - 1] = 1
	for i in range(n - 2, -1, -1):
		for j in range(m - 2, -1, -1):
			if grid[i][j] == '.':
				dp[i][j] = 0
			else:
				dp[i][j] = 1
				if j - 1 >= 0:
					dp[i][j] = dp[i][j] + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
	ans = 0
	for z in dp:
		ans += sum(z)
	print(ans)
t = int(input())
for test in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	grid = []
	for i in range(n):
		ch = input()
		temp = []
		for x in ch:
			temp.append(x)
		grid.append(temp)
	solve_2(grid)


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	matrix = []
	for i in range(n):
		matrix.append(input())
	ans = [[0 for i in range(m)] for j in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if matrix[i][j] == '*':
				if j < m - 2 and i > 0:
					if matrix[i][j + 1] == matrix[i][j + 2] == matrix[i - 1][j + 1] == '*':
						ans[i - 1][j + 1] += 1 + min(ans[i][j], ans[i][j + 1], ans[i][j + 2])
				ans[i][j] += 1
	total = 0
	for i in range(n):
		for j in range(m):
			total += ans[i][j]
	print(total)


import math
from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [[0] * m for i in range(n)]
	l1 = [[0] * m for i in range(n)]
	l2 = [[0] * m for i in range(n)]
	for i in range(n):
		s = str(input())
		for j in range(m):
			if s[j] == '*':
				l[i][j] = 1
				l1[i][j] = 1
				l2[i][j] = 1
	for i in range(1, n):
		for j in range(1, m):
			if l[i][j] == 1:
				l1[i][j] = min(l1[i - 1][j], l1[i][j - 1]) + 1
		for j in range(m - 2, -1, -1):
			if l[i][j] == 1:
				l2[i][j] = min(l2[i][j + 1], l2[i - 1][j]) + 1
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += min(l1[i][j], l2[i][j])
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		temp = input()
		mat.append(temp)
	c = 0
	dp = [[0 for x in range(m)] for y in range(n)]
	for i in range(n):
		temp = 0
		for j in range(m):
			if mat[i][j] == '*':
				temp += 1
			dp[i][j] = temp

	def isvalid(x1, y1, x2, y2):
		if x1 < 0 or x1 >= n or y1 < 0 or (y1 >= m) or (y2 < 0) or (y2 >= m):
			return False
		return True

	def allstars(x1, y1, x2, y2):
		if y1 == 0:
			if dp[x1][y2] == y2 - y1 + 1:
				return True
			else:
				return False
		elif dp[x1][y2] - dp[x1][y1 - 1] == y2 - y1 + 1:
			return True
		return False
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '*':
				x1 = i
				y1 = j
				x2 = i
				y2 = j
				while 1:
					if isvalid(x1, y1, x2, y2):
						if allstars(x1, y1, x2, y2):
							c += 1
							x1 += 1
							y1 -= 1
							x2 += 1
							y2 += 1
						else:
							break
					else:
						break
	print(c)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append(input())
	ans = [[0 for i in range(m)] for j in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if a[i][j] == '*':
				if j < m - 2 and i > 0:
					if a[i][j] == a[i - 1][j + 1] == a[i][j + 2] == a[i][j + 1] == '*':
						ans[i - 1][j + 1] += 1 + min(ans[i][j], ans[i][j + 1], ans[i][j + 2])
				ans[i][j] += 1
	total = 0
	for i in range(n):
		total += sum(ans[i])
	print(total)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	li = []
	for i in range(n):
		li.append(list(input()))
	dp = [[0 for i in range(m)] for j in range(n)]
	for i in reversed(range(n)):
		for j in reversed(range(m)):
			if li[i][j] == '*':
				if i + 1 < n and j - 1 >= 0 and (j + 1 < m):
					dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
				else:
					dp[i][j] = 1
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += dp[i][j]
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for x in range(n)]
	ans = 0
	for j in range(m):
		w = 0
		for i in range(n):
			w = min((w, j, m - j - 1))
			for k in range(w + 1):
				if a[i][j + k] == '.' or a[i][j - k] == '.':
					w = k - 1
					break
			ans += 1 + w
			w += 1
	print(ans)


def findTheSpruce(matrix):
	total = 0
	dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
	for col in range(len(matrix[0])):
		dp[-1][col] = 1 if matrix[-1][col] == '*' else 0
		total += dp[-1][col]
	for row in range(len(matrix) - 2, -1, -1):
		for col in range(len(matrix[0])):
			if matrix[row][col] == '*':
				minimum = dp[row + 1][col]
				if col == 0:
					minimum = 0
				else:
					minimum = min(minimum, dp[row + 1][col - 1])
				if col == len(matrix[0]) - 1:
					minimum = 0
				else:
					minimum = min(minimum, dp[row + 1][col + 1])
				dp[row][col] = 1 + minimum
				total += dp[row][col]
	return total
testcases = int(input().strip())
for _ in range(testcases):
	(n, m) = map(int, input().strip().split())
	matrix = []
	for i in range(n):
		matrix.append(input().strip())
	print(findTheSpruce(matrix))


import sys
import os
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		s = input()
		arr.append(s)
	dp = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		for j in range(m):
			if arr[i][j] == '*':
				dp[i][j] = dp[i][j - 1] + 1
			elif j == 0:
				if arr[i][j] == '*':
					dp[i][j] = 1
				else:
					dp[i][j] = 0
			else:
				dp[i][j] = dp[i][j - 1]
	ans = 0
	for x in range(n):
		for y in range(m):
			if arr[x][y] == '.':
				continue
			for level in range(min(n - x, m - y, y + 1)):
				k = dp[x + level][y + level]
				if y - level - 1 < 0:
					k1 = 0
				else:
					k1 = dp[x + level][y - level - 1]
				if k - k1 != level * 2 + 1:
					break
				ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	dp = [[0] * m for i in range(n)]
	ans = 0
	left = [[0] * m for i in range(n)]
	right = [[0] * m for i in range(n)]
	for i in range(n):
		l = list(input())
		a.append(l)
		for j in range(m):
			if l[j] == '*':
				if j - 1 >= 0:
					left[i][j] = left[i][j - 1] + 1
				else:
					left[i][j] = 1
		for j in range(m - 1, -1, -1):
			if l[j] == '*':
				if j + 1 < m:
					right[i][j] = right[i][j + 1] + 1
				else:
					right[i][j] = 1
	for i in range(n):
		j = 0
		chetchik = 0
		while j < m:
			if a[i][j] == '*':
				dp[i][j] = 1
				(lefts, rights) = (left[i][j], right[i][j])
				add = 0
				if i - 1 >= 0:
					add = dp[i - 1][j]
				if lefts != 1 and rights != 1:
					if min(lefts, rights) - 1 > add:
						dp[i][j] = add + 1
					else:
						dp[i][j] = min(lefts, rights)
				ans += dp[i][j]
			j += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	t = []
	for i in range(n):
		a.append(input())
		x = []
		s = 0
		for j in a[i]:
			if j == '*':
				s += 1
			x.append(s)
		t.append(x)
	ans = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == '*':
				k = 1
			else:
				continue
			while k <= n - i:
				l = j - k + 1
				h = j + k - 1
				f = i + k - 1
				if l >= 0 and h < m:
					if l == 0:
						s = t[f][h]
					else:
						s = t[f][h] - t[f][l - 1]
					if s == h - l + 1:
						k += 1
					else:
						break
				else:
					break
			ans += k - 1
	print(ans)


import sys
import math
from collections import defaultdict as ddict
from collections import deque
import heapq
from queue import Queue
from copy import deepcopy
from bisect import bisect_left as bl
from bisect import bisect_right as br
import os
fast_inp = lambda : sys.stdin.readline().rstrip('\n')
read_l = lambda : fast_inp().split(' ')
read_li = lambda : list(map(int, fast_inp().split(' ')))
read_lf = lambda : list(map(float, fast_inp().split(' ')))
read_i = lambda : int(fast_inp())
read_f = lambda : float(fast_inp())
read = lambda : fast_inp()
DEBUG = True

def debug(**kwargs):
	if not DEBUG:
		return
	print('=' * 20)
	for (k, v) in kwargs.items():
		print(f'\t{k}:{v}\t')
	print('=' * 20)

def print_mat(mat):
	for row in mat:
		print(*row)

def solve() -> None:
	(n, m) = read_li()
	matrix = [list(read()) for x in range(n)]
	dp = []
	for i in range(n):
		dp.append([0] * m)
	cnt = 0
	for i in range(n)[::-1]:
		for j in range(m)[::-1]:
			if matrix[i][j] == '*':
				dp[i][j] = 1
				if not (i + 1 >= n or j - 1 < 0 or j + 1 >= m):
					(f1, f2, f3) = (dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])
					mn = min(f1, f2, f3)
					dp[i][j] += mn
				cnt += dp[i][j]
	print(cnt)
t = read_i()
for _ in range(t):
	solve()


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	dp = [[0] * m for i in range(n)]
	matric = [input() for i in range(n)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if matric[i][j] == '*':
				if not (i == n - 1 or j == 0 or j == m - 1):
					dp[i][j] = 1 + min(dp[i + 1][j + 1], dp[i + 1][j - 1], dp[i + 1][j])
				else:
					dp[i][j] = 1
			ans += dp[i][j]
	print(ans)
	t -= 1


t = int(input())
for _t in range(t):
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		grid.append(input())
	dp = [[0 for i in range(m)] for j in range(n)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if grid[i][j] == '*':
				if i == n - 1 or j == 0 or j == m - 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
			else:
				dp[i][j] = 0
			ans += dp[i][j]
	print(ans)


import sys
import math, bisect, operator
(inf, m) = (float('inf'), 10 ** 9 + 7)
sys.setrecursionlimit(10 ** 6)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.readline())
neo = lambda : map(int, sys.stdin.readline().split())
Neo = lambda : list(map(int, sys.stdin.readline().split()))
for _ in range(I()):
	(n, m) = neo()
	A = [input() for i in range(n)]
	dp = [[0] * m for j in range(n)]
	Ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if A[i][j] == '*':
				dp[i][j] = 1
				if i + 1 < n and j - 1 > -1 and (j + 1 < m):
					dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1
			Ans += dp[i][j]
	print(Ans)


from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def MOD():
	return pow(10, 9) + 7

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')
for _ in range(INI()):
	(n, m) = INL()
	X = []
	for _ in range(n):
		X.append(list(input()))
	D = [[0 for _ in range(m)] for _ in range(n)]
	for _ in range(n - 1, -1, -1):
		for __ in range(m - 1, -1, -1):
			if _ + 1 < n and __ + 1 < m and (-1 < __ - 1) and (X[_][__] == '*'):
				D[_][__] = min(D[_ + 1][__ - 1], D[_ + 1][__], D[_ + 1][__ + 1]) + 1
			elif X[_][__] == '*':
				D[_][__] = 1
	ans = 0
	for _ in range(n):
		ans += sum(D[_])
	OPS(ans)


def checkStar(char):
	if char == '.':
		return 0
	else:
		return 1
matrix = list()
for t in [0] * int(input()):
	(n, m) = map(int, input().split())
	matrix = [input() for _ in [0] * n]
	for i in range(n):
		matrix[i] = list(map(checkStar, matrix[i]))
	for i in range(n - 1, 0, -1):
		for j in range(1, m - 1):
			if matrix[i][j - 1] != 0 and matrix[i][j] != 0 and (matrix[i][j + 1] != 0) and (matrix[i - 1][j] != 0):
				matrix[i - 1][j] += min(matrix[i][j - 1], matrix[i][j], matrix[i][j + 1])
	count = sum([sum(i) for i in matrix])
	print(count)


import sys
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = []
	for j in range(n):
		a.append(sys.stdin.readline().strip())
	dp = [[0 for j in range(m)] for k in range(n)]
	s = 0
	for j in range(n):
		for k in range(m):
			if a[j][k] == '*':
				if j > 0 and k > 1:
					dp[j][k] = 1 + min(dp[j - 1][k - 1], dp[j][k - 1], dp[j][k - 2])
				else:
					dp[j][k] = 1
			s = s + dp[j][k]
	print(s)


import sys, time

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_line():
	return sys.stdin.readline().strip()

def find(mat):
	count = 0
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if mat[i][j] == '.':
				mat[i][j] = 0
			elif j == 0 or j == m - 1 or i == n - 1:
				mat[i][j] = 1
			else:
				min_val = min(mat[i + 1][j - 1], mat[i + 1][j], mat[i + 1][j + 1])
				mat[i][j] = min_val + 1
			count += mat[i][j]
	return count
res = []
for _ in range(get_int()):
	(n, m) = get_ints()
	mat = []
	for i in range(n):
		mat.append(list(get_line()))
	res.append(str(find(mat)))
sys.stdout.write('\n'.join(res))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = [input() for i in range(n)]
	a = [[0] * m for i in range(n)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if s[i][j] == '*':
				a[i][j] = 1
				if i < n - 1 and j < m - 1 and (j > 0):
					if s[i + 1][j] == '*' and s[i + 1][j + 1] == '*' and (s[i + 1][j - 1] == '*'):
						a[i][j] += min([a[i + 1][j + 1], a[i + 1][j], a[i + 1][j - 1]])
			ans += a[i][j]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[*input()] for _ in range(n)]
	ans = 0
	l = [[0] * m for _ in range(n)]
	r = [[0] * m for _ in range(n)]
	for i in range(n):
		for j in range(m):
			l[i][j] = 1 if a[i][j] == '*' else 0
			r[i][j] = 1 if a[i][j] == '*' else 0
	for i in range(n):
		for j in range(1, m):
			if l[i][j]:
				l[i][j] += l[i][j - 1]
	for i in range(n):
		for j in range(m - 2, -1, -1):
			if r[i][j]:
				r[i][j] += r[i][j + 1]
	ans = 0
	for i in range(n):
		for j in range(m):
			nx = 1
			if l[i][j]:
				for k in range(i, n):
					if l[k][j] - 1 >= nx // 2 and r[k][j] - 1 >= nx // 2:
						ans += 1
						nx += 2
					else:
						break
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	dp = [[0 for i in range(m + 1)] for i in range(n)]
	for i in range(n):
		for j in range(m):
			if l[i][j] == '*':
				dp[i][j + 1] = 1 + dp[i][j]
			else:
				dp[i][j + 1] = dp[i][j]
	ans = 0
	for i in range(n):
		for j in range(m):
			c = 1
			d = 0
			for b in range(i, n):
				(x, y) = (j - d, j + d)
				if x >= 0 and y <= m - 1:
					if dp[b][y + 1] - dp[b][x] == c:
						ans += 1
					else:
						break
				else:
					break
				c += 2
				d += 1
	print(ans)


import sys
m = {'*': 1, '.': 0}

def sip():
	return sys.stdin.readline().rstrip()

def gen_test_cases():
	num_tests = int(sip())
	for i in range(num_tests):
		(height, width) = map(int, sip().split(' '))
		arr = [[m[c] for c in line] for line in [sys.stdin.readline().rstrip() for x in range(height)]]
		yield (height, width, arr)
for (h, w, mc) in gen_test_cases():
	for y in range(1, h):
		for x in range(1, w - 1):
			if mc[y][x] != 0:
				r = min(mc[y][x - 1], mc[y - 1][x])
				if r:
					mc[y][x] = r + 1
		for x in reversed(range(w - 1)):
			if mc[y][x] != 0:
				mc[y][x] = min(mc[y][x], mc[y][x + 1] + 1)
	count = sum([sum(mc[y]) for y in range(h)])
	print(count)


def solve():
	(n, m) = map(int, input().split())
	s = [str(input()) for i in range(n)]
	dp = [[0 for j in range(m)] for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(0, m):
			if s[i][j] == '*':
				if j == 0 or j == m - 1 or i == n - 1:
					dp[i][j] = 1
				else:
					dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1
	print(sum([sum(dp[i]) for i in range(n)]))
for tt in range(int(input())):
	solve()


def count_spruce(mat):
	ans = 0
	dp = {}
	for i in range(len(mat)):
		for j in range(len(mat[i])):
			size = spruceSize(mat, i, j, dp)
			ans += dp[i, j]
	return ans

def spruceSize(mat, i, j, dp):
	key = (i, j)
	if key in dp:
		return dp[key]
	if i >= len(mat) or j < 0 or j >= len(mat[i]):
		dp[key] = 0
		return 0
	minchilddepth = float('inf')
	if mat[i][j] == '.':
		dp[key] = 0
		return 0
	for jj in range(j - 1, j + 2):
		minchilddepth = min(minchilddepth, spruceSize(mat, i + 1, jj, dp))
	dp[key] = 1 + minchilddepth
	return dp[key]
t = int(input())
for c in range(t):
	inp = str(input())
	comps = inp.split()
	n = int(comps[0])
	m = int(comps[1])
	mat = []
	for row in range(n):
		mat.append(str(input()))
	print(count_spruce(mat))


t = int(input())
for _ in range(0, t):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(0, n):
		a.append(input())
	ml = [[0 for _ in range(m + 1)] for _ in range(n)]
	for i in range(0, n):
		for j in range(0, m):
			if a[i][j] == '*':
				ml[i][j + 1] = ml[i][j] + 1
			else:
				ml[i][j + 1] = 0
	ans = 0
	for i in range(0, n):
		for j in range(0, m):
			if a[i][j] == '*':
				for k in range(0, min(n - i, m - j)):
					if ml[i + k][j + k + 1] >= 2 * k + 1:
						ans = ans + 1
					else:
						break
	print(ans)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def cal(r, p, q, l, cnt, n, m, dp, visit):
	if r >= len(l):
		return
	if p < 0 or q >= m:
		return
	flag = 0
	if p == 0:
		if dp[r][q] != q - p + 1:
			flag = 1
	elif dp[r][q] - dp[r][p - 1] != q - p + 1:
		flag = 1
	if flag:
		return
	else:
		cnt[0] += 1
		cal(r + 1, p - 1, q + 1, l, cnt, n, m, dp, visit)

def main():
	try:
		(n, m) = In()
		l = []
		for i in range(n):
			l.append(Sn())
		cnt = [0]
		dp = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			cn = 0
			for j in range(m):
				if l[i][j] == '*':
					cn += 1
				dp[i][j] = cn
		answer = 0
		for x in range(n):
			for y in range(m):
				if l[x][y] == '.':
					continue
				for k in range(min(n - x, m - y, y + 1)):
					if y - k - 1 < 0:
						test = 0
					else:
						test = dp[x + k][y - k - 1]
					if dp[x + k][y + k] - test != 2 * k + 1:
						break
					answer += 1
		print(answer)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


def findSpruces(matrix, n, m):
	counts = [[0] * (m + 2) for _ in range(n + 1)]
	for x in range(1, n + 1):
		for y in range(1, m + 1):
			if matrix[n - x][y - 1] != '*':
				continue
			a = counts[x - 1][y - 1]
			b = counts[x - 1][y]
			c = counts[x - 1][y + 1]
			counts[x][y] = min(a, b, c) + 1
	return sum([item for sublist in counts for item in sublist])
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	matrix = []
	for _ in range(n):
		matrix.append(input())
	print(findSpruces(matrix, n, m))


def f(x: int):
	return x % 2 + x // 2

def find_spruce(n: int, m: int, field: list):
	res = 0
	temp_field = [[0 for j in range(m)] for i in range(n)]
	for j in range(m):
		if field[0][j] == '*':
			temp_field[0][j] = 1
			res += temp_field[0][j]
	for i in range(1, n):
		seq = 0
		for j in range(m):
			if field[i][j] == '*':
				seq += 1
			else:
				seq = 0
				continue
			if temp_field[i - 1][j - 1] != 0 and seq >= 3 and (f(seq) - temp_field[i - 1][j - 1] >= 1):
				temp_field[i][j] = temp_field[i - 1][j - 1] + 1
			elif temp_field[i - 1][j - 1] != 0 and seq >= 3:
				temp_field[i][j] = f(seq)
			else:
				temp_field[i][j] = 1
			res += temp_field[i][j]
	return res
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	field = []
	for j in range(n):
		field.append(input())
	print(find_spruce(n, m, field))


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, m) = map(int, input().split())
	TREE = [input().strip() for i in range(n)]
	DP = [[0] * (m + 2) for i in range(n + 2)]
	for i in range(n):
		for j in range(m):
			if TREE[i][j] == '*':
				DP[i][j] = 1
	for k in range(1, 250):
		for i in range(k, n):
			for j in range(k, m - k):
				if k <= min(DP[i][j], DP[i][j - 1], DP[i][j + 1], DP[i - 1][j]):
					DP[i][j] = k + 1
	ANS = 0
	for dp in DP:
		ANS += sum(dp)
	print(ANS)


def solve():
	(n, m) = map(int, input().split())
	matrix = []
	value = [[0 for x in range(m)] for y in range(n)]
	for q in range(n):
		matrix.append(list(input()))
	answer = 0
	for i in range(n - 1, -1, -1):
		for j in range(m):
			if matrix[i][j] != '*':
				continue
			counter = 0
			answer += 1
			if i + 1 < n:
				if j - 1 >= 0:
					if matrix[i + 1][j - 1] == '*':
						counter += 1
				if matrix[i + 1][j] == '*':
					counter += 1
				if j + 1 < m:
					if matrix[i + 1][j + 1] == '*':
						counter += 1
			answer -= 1
			if counter == 3:
				mini = 100000000000000000000000000
				if j - 1 >= 0:
					if matrix[i + 1][j - 1] == '*':
						mini = min(mini, value[i + 1][j - 1])
				if matrix[i + 1][j] == '*':
					mini = min(mini, value[i + 1][j])
				if j + 1 < m:
					if matrix[i + 1][j + 1] == '*':
						mini = min(mini, value[i + 1][j + 1])
				value[i][j] = mini + 1
			else:
				value[i][j] = 1
			answer += value[i][j]
	print(answer)
for _ in range(int(input())):
	solve()


from sys import stdin
from collections import defaultdict, Counter

def iinput():
	return int(stdin.readline())

def minput():
	return map(int, stdin.readline().split())

def linput():
	return list(map(int, stdin.readline().split()))
t = iinput()
while t:
	t -= 1
	(n, m) = minput()
	mat = []
	for i in range(n):
		mat.append(list(input()))
	dp = [[0 for _ in range(m)] for __ in range(n)]
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '*':
				dp[i][j] = 1
	for i in range(n - 2, -1, -1):
		for j in range(1, m - 1):
			if dp[i][j] == 1:
				dp[i][j] += min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
	spruce = 0
	for i in range(n):
		spruce += sum(dp[i])
	print(spruce)


import sys
import math

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod
t = II()
for q in range(t):
	(n, m) = MI()
	l = []
	for i in range(n):
		l.append(list(SI()))
	ans = 0
	dp = [[0 for i in range(m)] for j in range(n)]
	le = [[0 for i in range(m)] for j in range(n)]
	ri = [[0 for i in range(m)] for j in range(n)]
	for i in range(n):
		count = 0
		for j in range(m):
			le[i][j] = count
			if l[i][j] == '*':
				dp[i][j] = 1
				count += 1
				ans += 1
			else:
				count = 0
		count = 0
		for j in range(m - 1, -1, -1):
			ri[i][j] = count
			if l[i][j] == '*':
				count += 1
			else:
				count = 0
	for i in range(1, n):
		for j in range(m):
			if l[i][j] == '*':
				x = le[i][j]
				y = ri[i][j]
				z = dp[i - 1][j]
				if z != 0 and min(x, y, (z - 1) // 2 + 1) != 0:
					ans += (min(x, y, (z - 1) // 2 + 1) * 2 + 1) // 2
					dp[i][j] = min(x, y, (z - 1) // 2 + 1) * 2 + 1
	print(ans)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	x = []
	for i in range(n):
		y = input()
		x.append(list(y))
	dp = []
	for i in range(n):
		dp.append([0] * m)
	for i in range(n):
		for j in range(m):
			if x[i][j] == '*':
				dp[i][j] = 1
	for i in range(n - 2, -1, -1):
		for j in range(m - 2, 0, -1):
			if dp[i][j] == 1:
				dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += dp[i][j]
	print(ans)
	t = t - 1


def find_the_spruce():
	for _ in range(int(input())):
		(n, m) = list(map(int, input().split()))
		arr = [[x for x in input()] for _ in range(n)]
		ans = [[0 for _ in range(m)] for _ in range(n)]
		for i in range(m):
			ans[n - 1][i] = 1 if arr[n - 1][i] == '*' else 0
		for i in range(n - 2, -1, -1):
			for j in range(m):
				ans[i][j] += 1 if arr[i][j] == '*' else 0
				if 1 <= j < m - 1 and arr[i][j] == '*':
					min_el = ans[i + 1][j - 1:j + 2]
					ans[i][j] += min(min_el)
		ans_2 = 0
		for i in range(n):
			ans_2 += sum(ans[i])
		print(ans_2)
find_the_spruce()


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = ri()
	for _ in range(tc):
		(n, m) = ria()
		z = []
		ans = 0
		pref = []
		suff = []
		for i in range(n):
			t = rs()
			ps = []
			ss = []
			z.append(t)
			c = 0
			for j in range(m):
				if j - 1 < 0 or t[j - 1] == '.':
					c = 0
				else:
					c += 1
				ps.append(c)
			c = 0
			for j in range(m - 1, -1, -1):
				if j + 1 >= m or t[j + 1] == '.':
					c = 0
				else:
					c += 1
				ss.append(c)
			ss = ss[::-1]
			pref.append(ps)
			suff.append(ss)
		for i in range(n):
			for j in range(m):
				if z[i][j] == '*':
					for x in range(n - i):
						if z[i + x][j] == '.' or pref[i + x][j] < x or suff[i + x][j] < x:
							break
						ans += 1
		wi(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, m) = I()
	ar = [list(input().strip()) for i in range(n)]
	ans = 0
	arr = [[0] * (m + 1) for i in range(n)]
	for i in range(n):
		arr[i][0] = int(ar[i][0] == '*')
		for j in range(1, m):
			arr[i][j] += (ar[i][j] == '*') + arr[i][j - 1]
	for i in range(n):
		for j in range(m):
			if ar[i][j] == '*':
				ans += 1
				(ci, cj) = (i + 1, j)
				x = 1
				while ci < n:
					if j + x < m and j - x - 1 >= -1 and (arr[ci][j + x] - arr[ci][j - x - 1] == 2 * x + 1):
						ci += 1
						ans += 1
					else:
						break
					x += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	num = [[] for _ in range(n)]
	tab = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		s = input()
		for j in s:
			num[i].append(j)
	co = 0
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			lis = []
			c1 = 0
			if num[i][j] == '*':
				co += 1
			if i + 1 < n and num[i][j] == '*':
				if num[i + 1][j] == '*':
					lis.append(tab[i + 1][j])
					c1 += 1
				if j - 1 >= 0:
					if num[i + 1][j - 1] == '*':
						lis.append(tab[i + 1][j - 1])
						c1 += 1
				if j + 1 < m:
					if num[i + 1][j + 1] == '*':
						lis.append(tab[i + 1][j + 1])
						c1 += 1
			if c1 == 3:
				co += 1
				tab[i][j] += 1
			if len(lis) == 3:
				lis.sort()
				co += lis[0]
				tab[i][j] += lis[0]
	print(co)


from itertools import accumulate

def main():
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().split())
		t = []
		for i in range(a):
			l = input()
			t.append(l)
		dp = [[0] * (b + 2) for i in range(a + 1)]
		ans = 0
		for i in range(a - 1, -1, -1):
			for j in range(1, b + 1):
				if t[i][j - 1] == '*':
					dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
				ans += dp[i][j]
		print(ans)
main()


from heapq import *
import typing
import sys
import math
import collections
import bisect
import itertools
import heapq
import decimal
import copy
import operator
INF = 10 ** 20
MOD = 10 ** 9 + 7

def ni():
	return int(sys.stdin.readline())

def ns():
	return map(int, sys.stdin.readline().split())

def na():
	return list(map(int, sys.stdin.readline().split()))

def na1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def main():
	t = ni()
	for ti in range(t):
		(h, w) = ns()
		mat = [list(input()) for _ in range(h)]
		cnt = [[-1 for _ in range(w)] for __ in range(h)]

		def dfs(y, x):
			if not (0 <= y < h and 0 <= x < w):
				return
			if cnt[y][x] != -1:
				return
			if mat[y][x] == '*':
				cnt[y][x] = 1
			else:
				cnt[y][x] = 0
				return
			if 0 < x < w - 1:
				if y + 1 >= h:
					return
				dfs(y + 1, x - 1)
				dfs(y + 1, x)
				dfs(y + 1, x + 1)
				cnt[y][x] += min(cnt[y + 1][x - 1], cnt[y + 1][x], cnt[y + 1][x + 1])
		for i in range(h):
			for j in range(w):
				dfs(i, j)
		ans = sum([sum(c) for c in cnt])
		print(ans)
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	fa = []
	for i in range(n):
		s = input()
		l.append(s)
		k = []
		for i in range(m):
			k.append(0)
		fa.append(k)
	ans = 0
	for i in range(n):
		for j in range(m):
			if l[i][j] == '*':
				f = 0
				x = j
				y = j
				som = 0
				while f == 0:
					if x > -1 and y < m:
						if l[i][x] == '*' and l[i][y] == '*':
							som += 1
							x -= 1
							y += 1
						else:
							f = 1
					else:
						f = 1
				fa[i][j] = som
	i = 0
	while i < n:
		j = 0
		while j < m:
			if fa[i][j] > 0:
				x = i
				som = 0
				h = 1
				while x < n:
					if fa[x][j] >= h:
						som += 1
					else:
						break
					x += 1
					h += 1
				ans += som
			j = j + 1
		i += 1
	print(ans)


t = int(input())
for _ in range(0, t):
	dp = {}
	(a, b) = map(int, input().split(' '))
	board = []
	for _ in range(a):
		board.append(list(input()))
	answer = 0

	def heightSpruce(y, x):
		if board[y][x] == '.':
			return 0
		if y == a - 1:
			return 1
		if (y, x) in dp:
			return dp[y, x]
		ans = 1
		startX = x - 1
		endX = x + 1
		if 0 <= startX and endX <= b - 1:
			minHeight = 1000
			minHeight = min(minHeight, heightSpruce(y + 1, startX))
			minHeight = min(minHeight, heightSpruce(y + 1, x))
			minHeight = min(minHeight, heightSpruce(y + 1, endX))
			ans = 1 + minHeight
			dp[y, x] = ans
		else:
			dp[y, x] = ans
		return dp[y, x]
	for y in range(a):
		for x in range(b):
			h = heightSpruce(y, x)
			answer += h
	print(answer)


import sys
input = lambda : sys.stdin.readline().rstrip()

def solve(n, m):
	L0 = []
	L1 = []
	num = [0 for i in range(m * n)]
	for i in range(n):
		grid = input()
		for j in range(m):
			if grid[j] == '*':
				c = i * m + j
				num[c] = 1
				if i >= 1 and 1 <= j < m - 1:
					L1.append(c)
	k = 1
	while L1:
		L0 = L1
		L1 = []
		for c in L0:
			if min(num[c], num[c - m], num[c - 1], num[c + 1]) == k:
				num[c] += 1
				L1.append(c)
		k += 1
	return sum(num)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	print(solve(n, m))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	c = [input()[:-1] for i in range(n)]
	c = [[1 if j == '*' else 0 for j in ci] for ci in c]
	ru = [[0] * (m + 1) for i in range(n)]
	for i in range(n):
		for j in range(m):
			ru[i][j + 1] = ru[i][j] + c[i][j]
	ans = 0
	for i in range(n):
		for j in range(m):
			for k in range(n):
				if not i + k < n or j + k + 1 > m or j - k < 0:
					break
				if ru[i + k][j + k + 1] - ru[i + k][j - k] == 2 * k + 1:
					ans += 1
				else:
					break
	print(ans)


t = int(input())
g = []
for x in range(t):
	(n, m) = input().split()
	l = []
	for y in range(int(n)):
		l.append(input())
	p = [[0] * (int(m) + 2) for i in range(int(n) + 1)]
	for i in range(int(n) - 1, -1, -1):
		for j in range(1, int(m) + 1):
			if l[i][j - 1] == '*':
				p[i][j] = min(p[i + 1][j - 1], p[i + 1][j], p[i + 1][j + 1]) + 1
	print(sum([sum(h) for h in p]))


import sys, os
import math
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def MI():
	return map(int, input().split())

def out(var):
	sys.stdout.write(str(var) + '\n')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	inp = []
	out = 0
	for i in range(n):
		inp.append(list(input()))
	mat = [[] for i in range(n)]
	for i in range(n):
		for j in range(m):
			k = 0
			while j - k >= 0 and j + k < m:
				if inp[i][j - k] == '*' and inp[i][j + k] == '*':
					k += 1
				else:
					break
			mat[i].append(k)
	for i in range(n):
		for j in range(m):
			k = 0
			while i + k < n:
				if mat[i + k][j] >= k + 1:
					k += 1
				else:
					break
			out += k
	print(out)


import sys
from itertools import accumulate
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
	(r, c) = map(int, input().split())
	arr = [None] * r
	pref = [[0] * c for _ in range(r)]
	for i in range(r):
		arr[i] = input()
		pref[i] = [1 if arr[i][j] == '*' else 0 for j in range(c)]
		pref[i] = list(accumulate(pref[i]))
	ans = 0
	for i in range(r):
		for j in range(c):
			if arr[i][j] == '.':
				continue
			for cur_row in range(i, r):
				relative_row = cur_row - i
				(left, right) = (j - relative_row, j + relative_row)
				if not 0 <= left < c or not 0 <= right < c:
					break
				star_cnt = pref[cur_row][right] - (pref[cur_row][left - 1] if left - 1 >= 0 else 0)
				if star_cnt != right - left + 1:
					break
				ans += 1
	print(ans)


(z, zz) = (input, lambda : list(map(int, z().split())))
fast = lambda : stdin.readline().strip()
zzz = lambda : [int(i) for i in fast().split()]
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))
from string import *
from re import *
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f
from bisect import bisect as bs
from bisect import bisect_left as bsl
from itertools import accumulate as ac

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0 and x != 2 or x == 0:
			return 0
	return 1

def dfs(u, visit, graph):
	visit[u] = 1
	for i in graph[u]:
		if not visit[i]:
			dfs(i, visit, graph)

def output(answer):
	stdout.write(str(answer))
num = int(fast())
for i in range(num):
	(n, m) = zzz()
	lst = []
	for i in range(n):
		lst.append(fast())
	dp = [[0] * (m + 2) for i in range(n + 1)]
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(1, m + 1):
			if lst[i][j - 1] == '*':
				dp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])
			ans += dp[i][j]
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	inp = []
	for i in range(n):
		s = input()
		inp.append(s)
	ans = 0
	R = []
	L = []
	for i in range(n):
		low = 0
		high = 0
		right = []
		left = []
		while high < m:
			if inp[i][high] == '*':
				while high < m and inp[i][high] == '*':
					high += 1
				for j in range(high - low):
					left.append(j)
					right.append(high - low - j - 1)
				low = high
			else:
				left.append(0)
				right.append(0)
				high += 1
				low += 1
		R.append(right)
		L.append(left)
	main = [[0 for i in range(m)]]
	for i in range(n):
		temp = []
		for j in range(m):
			if inp[i][j] == '*':
				x = min(main[i][j] + 1, min(L[i][j], R[i][j]) + 1)
				ans += x
				temp.append(x)
			else:
				temp.append(0)
		main.append(temp)
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	cnt = 0
	a = []
	dp = []
	for i in range(n):
		dpp = []
		x = input()
		a.append(x)
		for j in range(m):
			if a[i][j] == '*':
				dpp.append([1, 1])
			else:
				dpp.append([0, 0])
		dp.append(dpp)
	for i in range(n):
		for j in range(m):
			if a[i][j] == '.':
				continue
			if j != 0:
				dp[i][j][0] += dp[i][j - 1][0]
			cnt += 1
			if i != 0 and j != 0:
				for kk in range(1, dp[i - 1][j - 1][1] + 1):
					if dp[i][j][0] >= 2 * kk + 1:
						cnt += 1
						dp[i][j][1] = kk + 1
	print(cnt)


t = int(input())
ml = []
for ind in range(t):
	s = input()
	s = s.split()
	for i in range(len(s)):
		s[i] = int(s[i])
	n = s[0]
	m = s[1]
	a = []
	b = []
	for ind in range(m + 2):
		b.append(0)
	for ind in range(n + 2):
		a.append(b.copy())
	for i in range(n):
		s2 = input()
		for j in range(m):
			if s2[j] == '*':
				a[i + 1][j + 1] = -1
	ml.append([n, m, a])

def f(a, x, y):
	if a[y + 1][x + 1] == -1:
		a[y + 1][x + 1] = 1 + min([a[y + 2][x], a[y + 2][x + 1], a[y + 2][x + 2]])

def sum(a):
	s = 0
	for l in a:
		for x in l:
			s = s + x
	return s

def main():
	for e in ml:
		n = e[0]
		m = e[1]
		a = e[2]
		y = n - 1
		x = 0
		while y > -1:
			while x < m:
				f(a, x, y)
				x = x + 1
			x = 0
			y = y - 1
		print(sum(a))
main()


from sys import stdin, stdout

def II():
	return int(stdin.readline())

def SI():
	return stdin.readline()[:-1]

def MI():
	return map(int, stdin.readline().split())

def solve():
	(n, m) = MI()
	c = []
	l = [[0 for i in range(m)] for j in range(n)]
	r = [[0 for i in range(m)] for j in range(n)]
	for i in range(n):
		s = SI()
		c.append(s)
		(lcnt, rcnt) = (0, 0)
		for j in range(m):
			k = m - 1 - j
			if s[j] == '.':
				lcnt = 0
			else:
				l[i][j] = lcnt
				lcnt += 1
			if s[k] == '.':
				rcnt = 0
			else:
				r[i][k] = rcnt
				rcnt += 1
	ans = 0
	for i in range(n):
		for j in range(m):
			if c[i][j] == '.':
				continue
			ans += 1
			for h in range(1, n - i):
				if l[i + h][j] < h or r[i + h][j] < h:
					break
				ans += 1
	stdout.write('{} \n'.format(ans))
t = II()
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left
import math
from operator import itemgetter
from heapq import heapify, heappop, heappush
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(input()[:-1]))
	f = [[0 for j in range(m)] for i in range(n)]
	b = [[0 for j in range(m)] for i in range(n)]
	for i in range(n):
		c = 0
		for j in range(m):
			b[i][j] = c
			if l[i][j] == '*':
				c += 1
			else:
				c = 0
	for i in range(n - 1, -1, -1):
		c = 0
		for j in range(m - 1, -1, -1):
			f[i][j] = c
			if l[i][j] == '*':
				c += 1
			else:
				c = 0
	p = 0
	for i in range(n):
		for j in range(m):
			if l[i][j] == '*':
				p += 1
				a = 1
				for k in range(i + 1, n):
					if l[k][j] == '*' and b[k][j] >= a and (f[k][j] >= a):
						p += 1
						a += 1
					else:
						break
	print(p)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	c = []
	for _ in range(n):
		c.append(input())
	pt = [0] * m
	ans = 0
	for i in range(n):
		ct = [0] * m
		j = 0
		while j < m:
			if c[i][j] == '*':
				start = j
				while j < m and c[i][j] == '*':
					j += 1
				for k in range(start, j):
					ct[k] = min(pt[k] + 1, k + 1 - start, j - k)
			j += 1
		pt = ct.copy()
		ans += sum(ct)
	print(ans)