B. Find the Spruce

problem_index: B

time_limit: 1 second

memory_limit: 256 megabytes

solutions: ["for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tb = []\n\tfor i in range(n):\n\t\ta.append(input())\n\t\tb.append([0] * m)\n\ts = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tif i == n - 1:\n\t\t\t\t\tb[i][j] = 1\n\t\t\t\t\ts += 1\n\t\t\t\telif j == 0 or j == m - 1:\n\t\t\t\t\tb[i][j] = 1\n\t\t\t\t\ts += 1\n\t\t\t\telse:\n\t\t\t\t\tx = b[i + 1][j - 1:j + 2]\n\t\t\t\t\tb[i][j] = min(x) + 1\n\t\t\t\t\ts += b[i][j]\n\tprint(s)\n", "def find(mat):\n\tcount = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tif mat[i][j] == '.':\n\t\t\t\tmat[i][j] = 0\n\t\t\telif j == 0 or j == m - 1 or i == n - 1:\n\t\t\t\tmat[i][j] = 1\n\t\t\telse:\n\t\t\t\tmin_val = min(mat[i + 1][j - 1], mat[i + 1][j], mat[i + 1][j + 1])\n\t\t\t\tmat[i][j] = min_val + 1\n\t\t\tcount += mat[i][j]\n\treturn count\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmat = []\n\tfor i in range(n):\n\t\tmat.append(list(input().strip()))\n\tprint(find(mat))\n", "def spruce(arr, n, m):\n\tcnt = 0\n\tdp = [[0 for i in range(m)] for i in range(n)]\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] == '*':\n\t\t\t\tif j != 0 and j != m - 1 and (i != n - 1):\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\tcnt += dp[i][j]\n\treturn cnt\nfor i in range(int(input())):\n\t(a, b) = map(int, input().strip().split())\n\tblanck = []\n\tfor i in range(a):\n\t\tstring = input()\n\t\tblanck.append(string)\n\tprint(spruce(blanck, a, b))\n", "(n, m) = (0, 0)\nmatrix = list()\nfor t in range(int(input())):\n\t(n, m) = [int(num) for num in input().split()]\n\tmatrix = list()\n\tfor i in range(n):\n\t\tmatrix.append([0 if char == '.' else 1 for char in input()])\n\tfor i in range(n - 1, 0, -1):\n\t\tfor j in range(1, m - 1):\n\t\t\tif matrix[i][j - 1] != 0 and matrix[i][j] != 0 and (matrix[i][j + 1] != 0) and (matrix[i - 1][j] != 0):\n\t\t\t\tmatrix[i - 1][j] += min(matrix[i][j - 1], matrix[i][j], matrix[i][j + 1])\n\tcount = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tcount += matrix[i][j]\n\tprint(count)\n", "def readGenerator():\n\twhile True:\n\t\ttokens = input().split(' ')\n\t\tfor t in tokens:\n\t\t\tyield t\nreader = readGenerator()\n\ndef readWord():\n\treturn next(reader)\n\ndef readInt():\n\treturn int(next(reader))\n\ndef readFloat():\n\treturn float(next(reader))\n\ndef readLine():\n\treturn input()\n\ndef solve(n, m, c):\n\tk = 0\n\tl = []\n\tr = []\n\tfor rw in range(n):\n\t\tl.append([-1] * m)\n\t\tr.append([m] * m)\n\t\tfor cl in range(m):\n\t\t\tif c[rw][cl] == '.':\n\t\t\t\tl[rw][cl] = cl\n\t\t\telif cl > 0:\n\t\t\t\tl[rw][cl] = l[rw][cl - 1]\n\t\tfor cl in reversed(range(m)):\n\t\t\tif c[rw][cl] == '.':\n\t\t\t\tr[rw][cl] = cl\n\t\t\telif cl < m - 1:\n\t\t\t\tr[rw][cl] = r[rw][cl + 1]\n\tfor rw in range(n):\n\t\tfor cl in range(m):\n\t\t\tfor i in range(rw, n):\n\t\t\t\td = i - rw\n\t\t\t\tstart = cl - d\n\t\t\t\tend = cl + d\n\t\t\t\tif start < 0 or end > m - 1:\n\t\t\t\t\tbreak\n\t\t\t\tif l[i][cl] >= start or r[i][cl] <= end:\n\t\t\t\t\tbreak\n\t\t\t\tk += 1\n\treturn k\nt = readInt()\nfor _ in range(t):\n\t(n, m) = [readInt() for _ in range(2)]\n\tc = []\n\tfor i in range(n):\n\t\tc.append(readLine())\n\tprint(solve(n, m, c))\n", "I = input\nfor _ in [0] * int(I()):\n\t(n, m) = map(int, I().split())\n\ta = [I() for _ in [0] * n]\n\tb = [0] * 501\n\tr = 0\n\tfor s in a[::-1]:\n\t\tb = (0, *((s[i] < '.') * (min(b[i:i + 3]) + 1) for i in range(m)), 0)\n\t\tr += sum(b)\n\tprint(r)\n", "tcs = int(input())\nfor tc in range(tcs):\n\t(m, n) = list(map(int, input().split()))\n\tmn = list()\n\tli = list()\n\tans = 0\n\tfor i in range(m):\n\t\tinp = input()\n\t\tmn.append('.' + inp + '.')\n\tmn.append('.' + '.' * n + '.')\n\tli = [[1 if i == '*' else 0 for i in mn[j]] for j in range(m + 1)]\n\tfor i in range(m - 1, -1, -1):\n\t\tfor j in range(1, n + 1):\n\t\t\tif li[i][j]:\n\t\t\t\tli[i][j] += min(li[i + 1][j + 1], li[i + 1][j - 1], li[i + 1][j])\n\t\t\t\tans += li[i][j]\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\t(lst, cnt, dp) = ([input() for i in range(n)], 0, [[0 for i in range(m)] for j in range(n)])\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif lst[i][j] == '*':\n\t\t\t\tdp[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)\n\t\t\t\tcnt += dp[i][j]\n\tprint(cnt)\n", "T = int(input())\nfor t in range(T):\n\t(n, m) = map(int, input().split())\n\tgrid = []\n\tfor i in range(n):\n\t\tgrid.append(input())\n\tcounters = [[0 for i in range(m)] for j in range(n)]\n\tans = 0\n\tfor r in range(n - 1, -1, -1):\n\t\tfor c in range(m):\n\t\t\tif grid[r][c] == '*':\n\t\t\t\tcounters[r][c] = 1\n\t\t\t\tif r < n - 1 and c > 0 and (c < m - 1):\n\t\t\t\t\tcounters[r][c] += min([counters[r + 1][c - 1], counters[r + 1][c], counters[r + 1][c + 1]])\n\t\t\t\tans += counters[r][c]\n\tprint(ans)\n", "def solve():\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor i in range(n):\n\t\ta.append(input())\n\tdp = []\n\tfor i in range(n):\n\t\tdp.append([])\n\t\tfor j in range(m):\n\t\t\tdp[i].append((1 if a[i][j] == '*' else 0) if j == 0 else dp[i][j - 1] + (1 if a[i][j] == '*' else 0))\n\tanswer = 0\n\tfor x in range(n):\n\t\tfor y in range(m):\n\t\t\tif a[x][y] == '.':\n\t\t\t\tcontinue\n\t\t\tfor level in range(min(n - x, m - y, y + 1)):\n\t\t\t\tif dp[x + level][y + level] - (0 if y - level - 1 < 0 else dp[x + level][y - level - 1]) != level * 2 + 1:\n\t\t\t\t\tbreak\n\t\t\t\tanswer += 1\n\tprint(answer)\ntests = int(input())\nwhile tests > 0:\n\tsolve()\n\ttests = tests - 1\n", "from pprint import pprint\nt = int(input())\nfor _ in range(t):\n\t(n, m) = list(map(int, input().split()))\n\tmat = [0 for i in range(n)]\n\tdp = [[0] * m for i in range(n)]\n\tfor i in range(n):\n\t\tmat[i] = list(input())\n\tfor col in range(m):\n\t\tdp[n - 1][col] = 1 if mat[n - 1][col] == '*' else 0\n\tfor i in range(n - 2, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] == '*':\n\t\t\t\ta = dp[i + 1][j - 1] if j - 1 >= 0 else 0\n\t\t\t\tb = dp[i + 1][j]\n\t\t\t\tc = dp[i + 1][j + 1] if j + 1 < m else 0\n\t\t\t\tdp[i][j] = 1 + min(a, b, c)\n\tans = 0\n\tfor row in dp:\n\t\tans += sum(row)\n\tprint(ans)\n", "for _ in range(int(input())):\n\tk = [int(x) for x in input().split()]\n\ta = []\n\tfor i in range(k[0]):\n\t\ta.append(input())\n\tdp = []\n\tfor i in range(k[0]):\n\t\tt = []\n\t\tfor j in range(k[1]):\n\t\t\tt.append(0)\n\t\tdp.append(t)\n\ts = 0\n\tfor i in range(k[1]):\n\t\tif a[-1][i] == '*':\n\t\t\tdp[-1][i] = 1\n\t\t\ts += 1\n\tfor i in range(k[0] - 2, -1, -1):\n\t\tfor j in range(0, k[1]):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tif j == 0 or j == k[1] - 1:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\ts += dp[i][j]\n\tprint(s)\n", "t = int(input())\ni = 1\nwhile i <= t:\n\t[n, m] = list(map(int, input().split()))\n\tarr = []\n\tans = []\n\ttotal = 0\n\tfor j in range(n):\n\t\tarr.append(input())\n\t\tans.append([0 for k in range(m)])\n\tfor j in range(n - 1, -1, -1):\n\t\tfor k in range(m - 1, -1, -1):\n\t\t\tif arr[j][k] == '*':\n\t\t\t\ttotal += 1\n\t\t\t\tans[j][k] += 1\n\t\t\t\tstart = k - 1\n\t\t\t\tend = k + 1\n\t\t\t\tif start >= 0 and end <= m - 1 and (j + 1 <= n - 1):\n\t\t\t\t\tmini = min(ans[j + 1][k - 1], ans[j + 1][k], ans[j + 1][k + 1])\n\t\t\t\t\ttotal += mini\n\t\t\t\t\tans[j][k] += mini\n\tprint(total)\n\ti += 1\n", "def solve(mat, n, m):\n\tres = 0\n\tdp = [[1 for _ in range(m)] for _ in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] == '.':\n\t\t\t\tdp[i][j] = 0\n\tfor i in range(n - 2, -1, -1):\n\t\tfor j in range(1, m - 1):\n\t\t\tif dp[i][j] == 0:\n\t\t\t\tcontinue\n\t\t\tminh = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\tdp[i][j] = 1 + minh\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tres += dp[i][j]\n\treturn res\nt = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tmat = []\n\tfor _ in range(n):\n\t\trow = input()\n\t\tmat.append(row)\n\tprint(solve(mat, n, m))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tl = []\n\tres = 0\n\tpre = []\n\tfor i in range(n):\n\t\ts = input()\n\t\tv = [0] * m\n\t\tif s[0] == '.':\n\t\t\tv[0] = 1\n\t\telse:\n\t\t\tres += 1\n\t\tfor j in range(1, m):\n\t\t\tif s[j] == '*':\n\t\t\t\tres += 1\n\t\t\t\tv[j] = v[j - 1]\n\t\t\telse:\n\t\t\t\tv[j] = 1 + v[j - 1]\n\t\tl.append(s)\n\t\tpre.append(v)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif l[i][j] != '.':\n\t\t\t\tx = j - 1\n\t\t\t\ty = j + 1\n\t\t\t\tc = i + 1\n\t\t\t\twhile c < n and x >= 0 and (y < m):\n\t\t\t\t\tif x == 0:\n\t\t\t\t\t\tcur = pre[c][y]\n\t\t\t\t\telse:\n\t\t\t\t\t\tcur = pre[c][y] - pre[c][x - 1]\n\t\t\t\t\tif cur >= 1:\n\t\t\t\t\t\tbreak\n\t\t\t\t\telse:\n\t\t\t\t\t\tres += 1\n\t\t\t\t\t\tx -= 1\n\t\t\t\t\t\ty += 1\n\t\t\t\t\t\tc += 1\n\tprint(res)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmartix = [input() for i in range(n)]\n\tdp = [[0 for j in range(m)] for i in range(n)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif martix[i][j] == '*':\n\t\t\t\tif not (i == n - 1 or j == 0 or j == m - 1):\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1])\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\tans += dp[i][j]\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tmat = []\n\tans = [[0 for i in range(k)] for j in range(n)]\n\tfor i in range(n):\n\t\ttemp = input()\n\t\tmat.append(temp)\n\tfor i in range(k):\n\t\tif mat[n - 1][i] == '*':\n\t\t\tans[n - 1][i] = 1\n\tfor i in range(n - 2, -1, -1):\n\t\tif mat[i][0] == '*':\n\t\t\tans[i][0] = 1\n\t\tif mat[i][k - 1] == '*':\n\t\t\tans[i][k - 1] = 1\n\t\tfor j in range(1, k - 1):\n\t\t\tif mat[i][j] == '*':\n\t\t\t\th = 1 + min(ans[i + 1][j], ans[i + 1][j - 1], ans[i + 1][j + 1])\n\t\t\t\tans[i][j] = h\n\tres = 0\n\tfor i in range(n):\n\t\tfor j in range(k):\n\t\t\tres += ans[i][j]\n\tprint(res)\n", "import logging\nimport sys\nfrom inspect import currentframe\nsys.setrecursionlimit(10 ** 6)\ninput = sys.stdin.readline\nlogging.basicConfig(level=logging.DEBUG)\n\ndef dbg(*args):\n\tid2names = {id(v): k for (k, v) in currentframe().f_back.f_locals.items()}\n\tlogging.debug(', '.join((id2names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args)))\n\ndef solve():\n\t(n, m) = map(int, input().split())\n\ts = [input().rstrip() for _ in range(n)]\n\tdp = [[0] * m for _ in range(n)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif s[i][j] == '*':\n\t\t\t\tif i == n - 1 or j == 0 or j == m - 1:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\t\tans += 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\t\t\tans += dp[i][j]\n\tprint(ans)\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tsolve()\nmain()\n", "t = int(input())\nfor i in range(t):\n\t(n, m) = map(int, input().split())\n\tw = []\n\tfor j in range(n):\n\t\tl = input()\n\t\tl = list(l)\n\t\tw.append(l)\n\tdp = []\n\tfor j in range(n):\n\t\tdp.append([0])\n\t\tfor k in range(m):\n\t\t\tif w[j][k] == '*':\n\t\t\t\tdp[-1].append(1 + dp[-1][-1])\n\t\t\telse:\n\t\t\t\tdp[-1].append(dp[-1][-1])\n\tcnt = 0\n\tfor j in range(n):\n\t\tfor k in range(m):\n\t\t\tif w[j][k] == '*':\n\t\t\t\tht = 0\n\t\t\t\twhile ht + j < n and k - ht >= 0 and (k + ht < m):\n\t\t\t\t\tif dp[j + ht][k + ht + 1] - dp[j + ht][k - ht] == 2 * ht + 1:\n\t\t\t\t\t\tht += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\tcnt += ht\n\tprint(cnt)\n", "class Vertex:\n\n\tdef __init__(self, ch, q=0):\n\t\tself.ch = ch\n\t\tself.h = q\n\n\tdef set(self, q):\n\t\tself.h = q\nfor t in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tarr = [[Vertex(ch) for ch in input()] for _ in range(n)]\n\tcount = 0\n\tfor y in range(n - 1, -1, -1):\n\t\tfor x in range(m):\n\t\t\tif arr[y][x].ch == '.':\n\t\t\t\tcontinue\n\t\t\tif x == 0 or x == m - 1 or y == n - 1:\n\t\t\t\th = 1\n\t\t\telse:\n\t\t\t\th = min([arr[y + 1][x - 1].h, arr[y + 1][x].h, arr[y + 1][x + 1].h]) + 1\n\t\t\tarr[y][x].set(h)\n\t\t\tcount += h\n\tprint(count)\n", "import sys, math\nfrom collections import deque, defaultdict\nimport operator as op\nfrom functools import reduce\nI = sys.stdin.readline\n\ndef ii():\n\treturn int(I().strip())\n\ndef li():\n\treturn list(map(int, I().strip().split()))\n\ndef mi():\n\treturn map(int, I().strip().split())\n\ndef ncr(n, r):\n\tr = min(r, n - r)\n\tnumer = reduce(op.mul, range(n, n - r, -1), 1)\n\tdenom = reduce(op.mul, range(1, r + 1), 1)\n\treturn numer // denom\n\ndef gcd(x, y):\n\twhile y:\n\t\t(x, y) = (y, x % y)\n\treturn x\n\ndef valid(row, col, rows, cols, rcross, lcross):\n\treturn rows[row] == 0 and cols[col] == 0 and (rcross[col + row] == 0) and (lcross[col - row] == 0)\n\ndef div(n):\n\ttmp = []\n\tfor i in range(2, int(n ** 0.5) + 1):\n\t\tif n % i == 0:\n\t\t\tcnt = 0\n\t\t\twhile n % i == 0:\n\t\t\t\tn = n // i\n\t\t\t\tcnt += 1\n\t\t\ttmp.append((i, cnt))\n\tif n > 1:\n\t\ttmp.append((n, 1))\n\treturn tmp\n\ndef isPrime(n):\n\tif n <= 1:\n\t\treturn False\n\telif n <= 2:\n\t\treturn True\n\telse:\n\t\tflag = True\n\t\tfor i in range(2, int(n ** 0.5) + 1):\n\t\t\tif n % i == 0:\n\t\t\t\tflag = False\n\t\t\t\tbreak\n\t\treturn flag\n\ndef main():\n\tans = ''\n\tfor _ in range(ii()):\n\t\t(n, m) = mi()\n\t\ttmp = []\n\t\tfor i in range(n):\n\t\t\ttmp.append(I().strip())\n\t\tarr = []\n\t\tfor i in range(n):\n\t\t\ta = []\n\t\t\tfor j in range(m):\n\t\t\t\tif tmp[i][j] == '*':\n\t\t\t\t\ta.append(1)\n\t\t\t\telse:\n\t\t\t\t\ta.append(0)\n\t\t\tarr.append(a)\n\t\tfor i in range(n - 2, -1, -1):\n\t\t\tfor j in range(m):\n\t\t\t\tif arr[i][j] == 1:\n\t\t\t\t\tif j > 0 and j < m - 1:\n\t\t\t\t\t\tx = arr[i + 1][j]\n\t\t\t\t\t\ty = arr[i + 1][j + 1]\n\t\t\t\t\t\tz = arr[i + 1][j - 1]\n\t\t\t\t\t\tif x > 0 and y > 0 and (z > 0):\n\t\t\t\t\t\t\tarr[i][j] = min(x, y, z) + 1\n\t\tcnt = 0\n\t\tfor i in range(n):\n\t\t\tcnt += sum(arr[i])\n\t\tans += str(cnt) + '\\n'\n\tprint(ans)\nmain()\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\n\ndef main():\n\tfor _ in range(int(input())):\n\t\t(n, m) = map(int, input().split())\n\t\tarr = []\n\t\tfor _ in range(n):\n\t\t\tarr.append(list(input()))\n\t\tdp = [[0 for _ in range(m + 2)] for _ in range(n + 1)]\n\t\tans = 0\n\t\tfor r in range(n - 1, -1, -1):\n\t\t\tfor c in range(1, m + 1):\n\t\t\t\tif arr[r][c - 1] == '*':\n\t\t\t\t\tdp[r][c] = min([dp[r + 1][c], dp[r + 1][c - 1], dp[r + 1][c + 1]]) + 1\n\t\t\t\t\tans += dp[r][c]\n\t\tprint(ans)\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "def compute_spruce(grid, width, x, y):\n\theight = 1\n\twhile True:\n\t\tif x + height >= len(grid):\n\t\t\tbreak\n\t\tif width[x + height][y] >= height + 1:\n\t\t\theight += 1\n\t\telse:\n\t\t\tbreak\n\treturn height\nt = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tgrid = []\n\tfor _ in range(n):\n\t\tgrid.append(list(input()))\n\twidth = [[0 for _ in range(m)] for _ in range(n)]\n\tleft = [[0 for _ in range(m)] for _ in range(n)]\n\tright = [[0 for _ in range(m)] for _ in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tif grid[i][j] == '*':\n\t\t\t\tif j == m - 1:\n\t\t\t\t\tright[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tright[i][j] = 1 + right[i][j + 1]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif grid[i][j] == '*':\n\t\t\t\tif j == 0:\n\t\t\t\t\tleft[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tleft[i][j] = 1 + left[i][j - 1]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\twidth[i][j] = min(left[i][j], right[i][j])\n\ttotal = 0\n\tdp = [[0 for _ in range(m)] for _ in range(n)]\n\tfor j in range(m):\n\t\tif grid[0][j] == '*':\n\t\t\tdp[0][j] = 1\n\tfor i in range(1, n):\n\t\tfor j in range(m):\n\t\t\tdp[i][j] = min(dp[i - 1][j], width[i][j] - 1) + 1\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\ttotal += dp[i][j]\n\tprint(total)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\ntest_cases = 1\ntest_cases = int(input())\nfor _ in range(test_cases):\n\t(n, m) = map(int, input().split())\n\ta = [str(input()) for i in range(n)]\n\tl = [[0 for i in range(m)] for j in range(n)]\n\tr = [[0 for i in range(m)] for j in range(n)]\n\tfor i in range(n):\n\t\tcnt = 0\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tcnt += 1\n\t\t\telse:\n\t\t\t\tcnt = 0\n\t\t\tr[i][j] = cnt\n\tfor i in range(n):\n\t\tcnt = 0\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tcnt += 1\n\t\t\telse:\n\t\t\t\tcnt = 0\n\t\t\tl[i][j] = cnt\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tk = i\n\t\t\tcnt = 1\n\t\t\twhile k < n:\n\t\t\t\tif l[k][j] >= cnt and r[k][j] >= cnt:\n\t\t\t\t\tk += 1\n\t\t\t\t\tcnt += 1\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tans += k - i\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\n\ndef check(i, j, ls):\n\tglobal n, m, dp\n\tans = 0\n\tfor c in range(min(j + 1, n - i, m - j)):\n\t\tif dp[i + c][j + c] - dp[i + c][j - c] + (1 if ls[i + c][j - c] == '*' else 0) == 2 * (c + 1) - 1:\n\t\t\tans += 1\n\t\telse:\n\t\t\treturn ans\n\treturn ans\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmat = []\n\tfor i in range(n):\n\t\tmat.append(input())\n\tdp = [[0 for i in range(m)] for _ in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] == '*':\n\t\t\t\tdp[i][j] = 1 if j == 0 else dp[i][j - 1] + 1\n\t\t\telse:\n\t\t\t\tdp[i][j] = dp[i][max(j - 1, 0)]\n\tans = 0\n\tfor row in range(n):\n\t\tfor columb in range(m):\n\t\t\tif mat[row][columb] == '*':\n\t\t\t\tans += check(row, columb, mat)\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tl = []\n\tfor i in range(n):\n\t\tl.append(input())\n\tcount = 0\n\ttrees = dict()\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(0, m):\n\t\t\tif l[i][j] == '*':\n\t\t\t\tx = 0\n\t\t\t\tif i != n - 1 and j >= 1 and (j <= m - 2):\n\t\t\t\t\tif (i + 1, j - 1) in trees and (i + 1, j) in trees and ((i + 1, j + 1) in trees):\n\t\t\t\t\t\tx = min(trees[i + 1, j - 1], trees[i + 1, j], trees[i + 1, j + 1])\n\t\t\t\tcount += x + 1\n\t\t\t\ttrees[i, j] = 1 + x\n\tprint(count)\n", "def dfs(x, y):\n\tif sublist[x][y] > 0:\n\t\treturn sublist[x][y]\n\tflag = 0\n\tif x + 1 < n and y - 1 > -1 and (y + 1 < m):\n\t\tif matrix[x + 1][y - 1:y + 2] == '***':\n\t\t\tflag = 1\n\tif flag:\n\t\tsublist[x][y] = 1 + min(dfs(x + 1, y), dfs(x + 1, y - 1), dfs(x + 1, y + 1))\n\t\treturn sublist[x][y]\n\telse:\n\t\tsublist[x][y] = 1\n\t\treturn sublist[x][y]\ntestcase = int(input())\nfor i in range(testcase):\n\tnm = list(map(int, input().split()))\n\tn = nm[0]\n\tm = nm[1]\n\tsublist = [[0 for i in range(m)] for y in range(n)]\n\tmatrix = []\n\tcount = 0\n\tfor y in range(n):\n\t\tmatrix.append(input())\n\tfor a in range(n):\n\t\tfor b in range(m):\n\t\t\tif matrix[a][b] == '*':\n\t\t\t\tcount += dfs(a, b)\n\tprint(count)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tans = [[0 for j in range(m)] for i in range(n)]\n\tmat = [input() for i in range(n)]\n\tcount = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] == '*':\n\t\t\t\tif i == n - 1 or j == 0 or j == m - 1:\n\t\t\t\t\tans[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tans[i][j] = 1 + min(ans[i + 1][j], ans[i + 1][j + 1], ans[i + 1][j - 1])\n\t\t\t\tcount += ans[i][j]\n\tprint(count)\n", "from sys import stdin, stdout\nfor i in range(int(stdin.readline())):\n\t(n, m) = [int(x) for x in stdin.readline().split()]\n\tl = [[0] * m for j in range(0, n)]\n\tarr = [[0] * m for j in range(0, n)]\n\tfor rows in range(0, n):\n\t\tl[rows] = list(stdin.readline())\n\tcount = 0\n\tj = 1\n\tfor r in range(0, n):\n\t\tfor c in range(0, m):\n\t\t\tif l[r][c] == '.':\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\tarr[r][c] = j\n\t\t\t\tj += 1\n\tfor r in range(0, n):\n\t\tfor c in range(0, m):\n\t\t\tif l[r][c] == '*':\n\t\t\t\tcount += 1\n\t\t\t\tfor k in range(1, n - r):\n\t\t\t\t\tif c - k >= 0 and c + k < m:\n\t\t\t\t\t\tif arr[r + k][c + k] - arr[r + k][c - k] + 1 == 2 * k + 1:\n\t\t\t\t\t\t\tcount += 1\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tbreak\n\tstdout.write(str(count) + '\\n')\n", "import math\nt = int(input())\n\ndef solve():\n\t(n, m) = list(map(int, input().split()))\n\tgraph = []\n\tdp = [[0] * (m + 1)]\n\tfor x in range(n):\n\t\tgraph.append(list(input()))\n\t\tdp.append([0] * (m + 1))\n\tans = 0\n\tfor x in range(n):\n\t\tcontinuity = 0\n\t\tfor y in range(m):\n\t\t\tif graph[x][y] == '*':\n\t\t\t\tcontinuity += 1\n\t\t\t\tdp[x + 1][y + 1] = min(dp[x][y] + 1, int((continuity - 1) / 2) + 1)\n\t\t\t\tans += dp[x + 1][y + 1]\n\t\t\telse:\n\t\t\t\tcontinuity = 0\n\treturn ans\nfor i in range(t):\n\toutput = solve()\n\tprint(output)\n", "t = int(input())\nwhile t:\n\t(n, m) = map(int, input().split())\n\ttable = [input() for _ in range(n)]\n\tdp = [[0 for _ in range(m)] for __ in range(n)]\n\tres = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(0, m):\n\t\t\tif table[i][j] == '*':\n\t\t\t\tif i == n - 1 or j == 0 or j == m - 1:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\t\tres += dp[i][j]\n\tprint(res)\n\tt -= 1\n", "def main():\n\timport sys\n\tinput = sys.stdin.readline\n\tt = int(input())\n\tfor _ in range(t):\n\t\t(n, m) = map(int, input().split())\n\t\tc = [input() for i in range(n)]\n\t\tC = [[0] * (m + 1) for i in range(n)]\n\t\tans = 0\n\t\tfor i in range(n):\n\t\t\tfor j in range(m):\n\t\t\t\tif c[i][j] == '*':\n\t\t\t\t\tans += 1\n\t\t\t\t\tC[i][j + 1] = C[i][j] + 1\n\t\tfor i in range(n):\n\t\t\tfor j in range(m):\n\t\t\t\tif c[i][j] == '*':\n\t\t\t\t\tfor k in range(1, n - i):\n\t\t\t\t\t\tif j - k < 0 or j + k >= m:\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\telif C[i + k][j + k + 1] - C[i + k][j - k] == k * 2 + 1:\n\t\t\t\t\t\t\tans += 1\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tbreak\n\t\tprint(ans)\nmain()\n", "import io\nimport os\nfrom collections import Counter, defaultdict, deque\n\ndef solve(R, C, grid):\n\tans = 0\n\tdp = [[0 for c in range(C)] for r in range(R)]\n\tfor r in reversed(range(R)):\n\t\tfor c in range(C):\n\t\t\tif grid[r][c] == '*':\n\t\t\t\tcount = max(dp[r][c], 1)\n\t\t\t\tif r < R - 1 and c > 0 and (c < C - 1):\n\t\t\t\t\tcount = max(count, min(dp[r + 1][c - 1], dp[r + 1][c], dp[r + 1][c + 1]) + 1)\n\t\t\t\tdp[r][c] = count\n\t\t\t\tans += count\n\tif False:\n\t\tprint()\n\t\tfor row in dp:\n\t\t\tprint('\\t'.join(map(str, row)))\n\treturn ans\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nTC = int(input())\nfor tc in range(1, TC + 1):\n\t(N, M) = [int(x) for x in input().split()]\n\tgrid = [list(input().decode().rstrip()) for i in range(N)]\n\tans = solve(N, M, grid)\n\tprint(ans)\n", "T = int(input())\nfor t in range(T):\n\t(N, M) = list(map(int, input().split()))\n\ta = [list(input()) for n in range(N)]\n\tans = 0\n\tfor i in range(N):\n\t\tfor j in range(M):\n\t\t\tif a[i][j] == '*':\n\t\t\t\ta[i][j] = 1\n\t\t\telif a[i][j] == '.':\n\t\t\t\ta[i][j] = 0\n\tfor i in range(N - 2, -1, -1):\n\t\tfor j in range(1, M - 1):\n\t\t\tif a[i][j] != 0:\n\t\t\t\ta[i][j] = min(a[i + 1][j - 1], a[i + 1][j], a[i + 1][j + 1]) + 1\n\tfor i in range(N):\n\t\tfor j in range(M):\n\t\t\tans += a[i][j]\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(r, c) = map(int, input().split())\n\tres = 0\n\tm = [[0 for i in range(c + 2)] for j in range(r + 1)]\n\tdata = [0 for i in range(r)]\n\tfor row in range(r):\n\t\tdata[row] = input()\n\tfor i in range(row, -1, -1):\n\t\tfor j in range(c):\n\t\t\tif data[i][j] == '*':\n\t\t\t\tm[i][j + 1] = min(m[i + 1][j], m[i + 1][j + 1], m[i + 1][j + 2]) + 1\n\tprint(sum([sum(i) for i in m]))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tinp = []\n\tout = 0\n\tfor i in range(n):\n\t\tinp.append(list(input()))\n\tmat = [[] for i in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tk = 0\n\t\t\twhile j - k >= 0 and j + k < m:\n\t\t\t\tif inp[i][j - k] == '*' and inp[i][j + k] == '*':\n\t\t\t\t\tk += 1\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tmat[i].append(k)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tk = 0\n\t\t\twhile i + k < n:\n\t\t\t\tif mat[i + k][j] >= k + 1:\n\t\t\t\t\tk += 1\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tout += k\n\tprint(out)\n", "for _ in range(int(input())):\n\t(n, m) = list(map(int, input().split()))\n\tarr = []\n\tc = 0\n\tfor i in range(n):\n\t\tz = list(input())\n\t\tc += z.count('*')\n\t\tarr.append(z)\n\tans = []\n\tfor i in range(n):\n\t\tans.append([0] * m)\n\tfor i in range(m):\n\t\tfor g in range(n):\n\t\t\tif arr[g][i] == '*':\n\t\t\t\tans[g][i] = 1\n\tfor i in range(n - 2, -1, -1):\n\t\tfor g in range(m):\n\t\t\tif arr[i][g] == '*':\n\t\t\t\tif g != 0 and g != m - 1:\n\t\t\t\t\tif arr[i + 1][g] == '*' and arr[i + 1][g - 1] == '*' and (arr[i + 1][g + 1] == '*'):\n\t\t\t\t\t\tans[i][g] += min(min(g, m - g - 1), min(ans[i + 1][g], ans[i + 1][g - 1], ans[i + 1][g + 1]))\n\ts = 0\n\tfor i in range(n):\n\t\tfor g in range(m):\n\t\t\ts += ans[i][g]\n\tprint(s)\n", "import sys, io, os, time\nfrom collections import defaultdict\nfrom collections import Counter\nfrom collections import deque\nfrom itertools import combinations\nfrom itertools import permutations\nimport bisect, math, heapq\nalphabet = 'abcdefghijklmnopqrstuvwxyz'\ninput = sys.stdin.readline\nfor ii in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tarr = []\n\tfor i in range(n):\n\t\tarr.append(list(map(str, input()))[:-1])\n\trowsum = []\n\tans = 0\n\tcolsum = [[0] * (m + 1) for i in range(n + 1)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] == '*':\n\t\t\t\tcolsum[i][j + 1] = colsum[i][j] + 1\n\t\t\t\tans += 1\n\t\t\telse:\n\t\t\t\tcolsum[i][j + 1] = colsum[i][j]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\ttemp = 0\n\t\t\tif arr[i][j] == '*':\n\t\t\t\toff = 1\n\t\t\t\tfor x in range(i + off, n):\n\t\t\t\t\tif 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):\n\t\t\t\t\t\toff += 1\n\t\t\t\t\t\ttemp += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\tans += temp\n\tprint(ans)\n", "from collections import defaultdict, deque\nimport sys\nimport bisect\ninput = sys.stdin.readline\nmod = 1000000007\nt = int(input())\nfor ii in range(t):\n\t(n, m) = map(int, input().split())\n\tMAP = [[i for i in input() if i != '\\n'] for i in range(n)]\n\tcount = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif MAP[i][j] == '*':\n\t\t\t\tcount += 1\n\tCOUNT0 = [[0] * m for i in range(n)]\n\tCOUNT1 = [[0] * m for i in range(n)]\n\tfor i in range(1, n):\n\t\tfor j in range(1, m):\n\t\t\tif MAP[i][j] == MAP[i][j - 1] == MAP[i - 1][j] == '*':\n\t\t\t\tCOUNT0[i][j] = min(COUNT0[i][j - 1], COUNT0[i - 1][j]) + 1\n\tfor i in range(1, n):\n\t\tfor j in range(m - 2, -1, -1):\n\t\t\tif MAP[i][j] == MAP[i][j + 1] == MAP[i - 1][j] == '*':\n\t\t\t\tCOUNT1[i][j] = min(COUNT1[i][j + 1], COUNT1[i - 1][j]) + 1\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tans += min(COUNT0[i][j], COUNT1[i][j])\n\tprint(ans + count)\n", "import os, sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ntry:\n\t(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))\nexcept:\n\tpass\nii1 = lambda : int(sys.stdin.readline().strip())\nis1 = lambda : sys.stdin.readline().strip()\niia = lambda : list(map(int, sys.stdin.readline().strip().split()))\nisa = lambda : sys.stdin.readline().strip().split()\nmod = int(1000000000.0 + 7)\nfrom math import inf\nfor _ in range(ii1()):\n\t(n, m) = iia()\n\tarr = []\n\tfor i in range(n):\n\t\tarr.append(is1())\n\tans = 0\n\tdp = [[0] * m for _ in range(n)]\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] == '*':\n\t\t\t\tif i == n - 1 or j == 0 or j == m - 1:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])\n\t\t\tans += dp[i][j]\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tarr = [list(input()) for i in range(n)]\n\tdp = [[0] * (m + 2) for i in range(n + 1)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(1, m + 1):\n\t\t\tif arr[i][j - 1] == '*':\n\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\tans += dp[i][j]\n\tprint(ans)\n", "t = int(input())\nfor z in range(t):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor i in range(n):\n\t\ttmp = input()\n\t\ta.append(tmp)\n\tsum = []\n\tkq = []\n\tans = int(0)\n\tfor i in range(n):\n\t\ttmp = []\n\t\ttmp1 = []\n\t\tfor j in range(m):\n\t\t\ttmp.append(int(0))\n\t\t\ttmp1.append(int(0))\n\t\tsum.append(tmp)\n\t\tkq.append(tmp1)\n\tfor i in range(n):\n\t\tif a[i][0] == '*':\n\t\t\tsum[i][0] = 1\n\t\telse:\n\t\t\tsum[i][0] = 0\n\tfor i in range(n):\n\t\tfor j in range(1, m):\n\t\t\tif a[i][j] == '.':\n\t\t\t\tsum[i][j] = 0\n\t\t\telse:\n\t\t\t\tsum[i][j] = sum[i][j - 1] + 1\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif n == 0 or m == 0:\n\t\t\t\tkq[i][j] = sum[i][j]\n\t\t\t\tans = ans + sum[i][j]\n\t\t\telse:\n\t\t\t\tif sum[i][j] != 0:\n\t\t\t\t\tkq[i][j] = min(kq[i - 1][j - 1] + 1, (sum[i][j] - 1) // 2 + 1)\n\t\t\t\telse:\n\t\t\t\t\tkq[i][j] = 0\n\t\t\t\tans = ans + kq[i][j]\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor __ in range(n):\n\t\ta.append(input())\n\tdp = [[1 if c == '*' else 0 for c in r] for r in a]\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tif dp[i][j] == 1 and i < n - 1 and (0 < j < m - 1):\n\t\t\t\tdp[i][j] += min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\tprint(sum((sum(d) for d in dp)))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tma = [input() for i in range(n)]\n\tdp = [[0 for j in range(m)] for i in range(n)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif ma[i][j] == '*':\n\t\t\t\tif i != n - 1 and j != 0 and (j != m - 1):\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1])\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\tans += dp[i][j]\n\tprint(ans)\n", "from sys import stdin\ninput = stdin.readline\n\ndef find(i, j):\n\tmi = 1000000.0\n\tfor h in range(2):\n\t\tif j - h < 0 or j + h >= m:\n\t\t\tmi = 0\n\t\t\tbreak\n\t\tmi = min(mi, processed[i + 1][j - h], processed[i + 1][j + h])\n\tprocessed[i][j] = mi + 1\n\ndef func():\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif grid[i][j] == '*':\n\t\t\t\tprocessed[i][j] = 1\n\tfor i in range(n - 2, -1, -1):\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tif grid[i][j] == '*':\n\t\t\t\tfind(i, j)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tans += processed[i][j]\n\tprint(ans)\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tgrid = [list(input()) for __ in range(n)]\n\tprocessed = [[0 for x in range(m)] for y in range(n)]\n\tfunc()\n", "def result(arr, n, board_number, m):\n\tsum = 0\n\tfor j in range(m):\n\t\tif arr[n - 1][j] == '*':\n\t\t\tboard_number[n - 1][j] = 1\n\t\telse:\n\t\t\tboard_number[n - 1][j] = 0\n\t\tsum += board_number[n - 1][j]\n\tfor i in range(n - 2, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] == '.':\n\t\t\t\tboard_number[i][j] = 0\n\t\t\telif j == 0 or j == m - 1:\n\t\t\t\tif arr[i][j] == '*':\n\t\t\t\t\tboard_number[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tboard_number[i][j] = 0\n\t\t\telse:\n\t\t\t\tboard_number[i][j] = 1 + min(board_number[i + 1][j], board_number[i + 1][j + 1], board_number[i + 1][j - 1])\n\t\t\tsum += board_number[i][j]\n\treturn sum\nno_tests = int(input())\nres = []\nfor i in range(no_tests):\n\tarr = []\n\tboard_number = []\n\tdimension = input().split()\n\t(n, m) = (int(dimension[0]), int(dimension[1]))\n\tfor row in range(n):\n\t\tread_arr = input()\n\t\ttmp = []\n\t\ttmp_board = []\n\t\tfor col in range(m):\n\t\t\ttmp.append(read_arr[col])\n\t\t\ttmp_board.append(0)\n\t\tarr.append(tmp)\n\t\tboard_number.append(tmp_board)\n\tres.append(result(arr, n, board_number, m))\nfor each in res:\n\tprint(each)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor i in range(n):\n\t\ta.append(input())\n\tcount = 0\n\tdp = []\n\tfor i in range(n):\n\t\tdp.append([])\n\t\tfor j in range(m):\n\t\t\tdp[i].append((0 if a[i][j] == '.' else 1) if j == 0 else dp[i][j - 1] + (0 if a[i][j] == '.' else 1))\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tfor k in range(min(n - i, m - j, j + 1)):\n\t\t\t\t\tif dp[i + k][j + k] - (0 if j - k - 1 < 0 else dp[i + k][j - k - 1]) == k * 2 + 1:\n\t\t\t\t\t\tcount += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\tprint(count)\n", "t = int(input())\nfor _ in range(t):\n\t(m, n) = [int(i) for i in input().split()]\n\tmatrix = []\n\tfor _ in range(m):\n\t\tmatrix.append(input())\n\tcount = [[0 for _ in range(n)] for _ in range(m)]\n\tres = 0\n\tfor i in range(m):\n\t\tstart = 0\n\t\tfor j in range(n):\n\t\t\tif matrix[i][j] == '*':\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\twhile start < j:\n\t\t\t\t\tL = j - start\n\t\t\t\t\tif L == 1:\n\t\t\t\t\t\tcount[i][start] = 1\n\t\t\t\t\t\tres += 1\n\t\t\t\t\telif i > 0 and count[i - 1][start + 1] >= L - 2:\n\t\t\t\t\t\tcount[i][start] = L\n\t\t\t\t\t\tres += (L + 1) // 2\n\t\t\t\t\telif i == 0:\n\t\t\t\t\t\tcount[i][start] = 1\n\t\t\t\t\t\tres += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tL = count[i - 1][start + 1] + 2\n\t\t\t\t\t\tcount[i][start] = L\n\t\t\t\t\t\tres += (L + 1) // 2\n\t\t\t\t\tstart += 1\n\t\t\t\tstart += 1\n\t\telse:\n\t\t\twhile start < n:\n\t\t\t\tL = n - start\n\t\t\t\tif L == 1:\n\t\t\t\t\tcount[i][start] = 1\n\t\t\t\t\tres += 1\n\t\t\t\telif i > 0 and count[i - 1][start + 1] >= L - 2:\n\t\t\t\t\tcount[i][start] = L\n\t\t\t\t\tres += (L + 1) // 2\n\t\t\t\telif i == 0:\n\t\t\t\t\tcount[i][start] = 1\n\t\t\t\t\tres += 1\n\t\t\t\telse:\n\t\t\t\t\tL = count[i - 1][start + 1] + 2\n\t\t\t\t\tcount[i][start] = L\n\t\t\t\t\tres += (L + 1) // 2\n\t\t\t\tstart += 1\n\tprint(res)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmatrix = [list(input()) for _ in range(n)]\n\tdp = [[0] * m for _ in range(n)]\n\tans = 0\n\ts = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif matrix[i][j] == '*':\n\t\t\t\tdp[i][j] = 1\n\t\t\t\tif i + 1 < n and j - 1 >= 0 and (j + 1 < m):\n\t\t\t\t\tdp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1\n\t\t\ts += dp[i][j]\n\tprint(s)\n", "from functools import lru_cache\nimport sys\nsys.setrecursionlimit(250000)\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\n\t@lru_cache(None)\n\tdef dfs(h, w):\n\t\tif 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] == '*'):\n\t\t\treturn min(dfs(h + 1, w - 1), dfs(h + 1, w), dfs(h + 1, w + 1)) + 1\n\t\telse:\n\t\t\treturn 1\n\t(n, m) = map(int, input().split())\n\ttree = [list(input()) for i in range(n)]\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif tree[i][j] == '*':\n\t\t\t\tans += dfs(i, j)\n\tprint(ans)\n", "ll = lambda : map(int, input().split())\nt = lambda : int(input())\nss = lambda : input()\nfor _ in range(t()):\n\t(n, m) = ll()\n\ta = []\n\tans = [0]\n\td = []\n\tfor i in range(n):\n\t\ts = ss()\n\t\ta.append(s)\n\t\td.append([0] * m)\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\td[i][j] += 1\n\t\t\t\tif j - 2 >= 0 and i - 1 >= 0 and (j >= 2):\n\t\t\t\t\tif a[i][j - 1] == a[i][j - 2] == '*' and a[i - 1][j - 1] == '*':\n\t\t\t\t\t\td[i - 1][j - 1] = min(d[i][j - 1], d[i][j], d[i][j - 2])\n\tfor i in range(n):\n\t\tans[0] += sum(d[i])\n\tprint(ans[0])\n", "import sys\nimport math, cmath\nimport bisect\nfrom functools import reduce, lru_cache\nfrom collections import Counter\nfrom itertools import groupby\n\ndef getN():\n\treturn int(input())\n\ndef getNM():\n\treturn map(int, input().split())\n\ndef getList():\n\treturn list(map(int, input().split()))\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\n\ndef index(a, x):\n\ti = bisect.bisect_left(a, x)\n\tif i != len(a) and a[i] == x:\n\t\treturn i\n\treturn False\n\ndef create_pref(arr):\n\tpref = [0] * len(arr)\n\tpref[0] = arr[0]\n\tfor i in range(1, len(arr)):\n\t\tpref[i] += pref[i - 1] + arr[i]\n\treturn pref\n\ndef modpow(x, n, m):\n\tif n == 0:\n\t\treturn 1 % m\n\tu = modpow(x, n // 2, m)\n\tu = u * u % m\n\tif n % 2 == 1:\n\t\tu = u * x % m\n\treturn u\nfor _ in range(getN()):\n\t(n, m) = getNM()\n\ttable = []\n\tfor i in range(n):\n\t\ts = input()\n\t\ttable.append([1 if x == '*' else 0 for x in s])\n\ttable_pref = [create_pref(table[i]) for i in range(n)]\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif table[i][j] == 1:\n\t\t\t\ts = 1\n\t\t\t\tfor k in range(1, m):\n\t\t\t\t\tif i + k >= n or j - k < 0 or j + k >= m:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tif table_pref[i + k][j + k] - (table_pref[i + k][j - k - 1] if j - k != 0 else 0) == (k + 1) * 2 - 1:\n\t\t\t\t\t\ts += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\tans += s\n\tprint(ans)\n", "from sys import stdin\nimport sys\ntt = int(stdin.readline())\nfor loop in range(tt):\n\t(n, m) = map(int, stdin.readline().split())\n\ta = []\n\tfor i in range(n):\n\t\ta.append(stdin.readline()[:-1])\n\tdp = [[0] * m for i in range(n)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tif i == n - 1 or j == 0 or j == m - 1:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])\n\t\t\tans += dp[i][j]\n\tprint(ans)\n", "def main():\n\n\tdef conv(ind):\n\t\tif ind == '.':\n\t\t\treturn 0\n\t\telse:\n\t\t\treturn 1\n\n\tdef check(x, y):\n\t\ttx = x\n\t\tty = y\n\t\theight = 0\n\t\tcount = 0\n\t\tbroke = False\n\t\twhile broke == False:\n\t\t\tif ty - height >= 0 and ty + height <= m - 1 and (tx + height <= n - 1):\n\t\t\t\tif ty - height == 0:\n\t\t\t\t\tnum1 = 0\n\t\t\t\telse:\n\t\t\t\t\tnum1 = dict1[tx + height][ty - height - 1]\n\t\t\t\tif dict1[tx + height][ty + height] - num1 == 1 + 2 * height:\n\t\t\t\t\tcount += 1\n\t\t\t\t\theight += 1\n\t\t\t\telse:\n\t\t\t\t\tbroke = True\n\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tbroke = True\n\t\t\t\tbreak\n\t\treturn count\n\tfor j in range(int(input())):\n\t\t(n, m) = map(int, input().split())\n\t\tmatr = []\n\t\tans = 0\n\t\tdict1 = {}\n\t\tfor s in range(n):\n\t\t\trow = [conv(k) for k in input()]\n\t\t\tmatr.append(row)\n\t\tfor s in range(n):\n\t\t\tpref = [matr[s][0]]\n\t\t\tfor i in range(1, m):\n\t\t\t\tpref.append(pref[-1] + matr[s][i])\n\t\t\tdict1[s] = pref\n\t\tfor s in range(n):\n\t\t\tfor i in range(m):\n\t\t\t\tans += check(s, i)\n\t\tprint(ans)\nmain()\n", "for t in range(int(input())):\n\t(r, c) = map(int, input().split())\n\ta = []\n\tfor i in range(r):\n\t\tstr = input()\n\t\ta.append(str)\n\tfront = [[0 for i in range(c)] for j in range(r)]\n\tback = [[0 for i in range(c)] for j in range(r)]\n\tcount = 0\n\tfor i in range(r):\n\t\tcount = 0\n\t\tfor j in range(c):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tcount += 1\n\t\t\t\tfront[i][j] = count\n\t\t\telse:\n\t\t\t\tcount = 0\n\t\t\t\tfront[i][j] = count\n\tfor i in range(r):\n\t\tcount = 0\n\t\tfor j in range(c - 1, -1, -1):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tcount += 1\n\t\t\t\tback[i][j] = count\n\t\t\telse:\n\t\t\t\tcount = 0\n\t\t\t\tback[i][j] = count\n\tadd = 0\n\tk = 0\n\tcount = 0\n\tfor i in range(r):\n\t\tfor j in range(c):\n\t\t\tk = i\n\t\t\tcount = 1\n\t\t\twhile k < r:\n\t\t\t\tif front[k][j] >= count and back[k][j] >= count:\n\t\t\t\t\tadd += 1\n\t\t\t\t\tk += 1\n\t\t\t\t\tcount += 1\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\tprint(add)\n", "I = input\nfor _ in [0] * int(I()):\n\ta = [I() for _ in [0] * int(I().split()[0])]\n\tb = [0] * 501\n\tr = 0\n\tfor s in a[::-1]:\n\t\tb = (0, *(x < '.' and min(b[i:i + 3]) + 1 for (i, x) in enumerate(s)), 0)\n\t\tr += sum(b)\n\tprint(r)\n", "a = int(input())\nfor o in range(a):\n\t(n, m) = map(int, input().split())\n\tpic = [0] * n\n\tfor i in range(n):\n\t\tpic[i] = [0] * m\n\tfor i in range(n):\n\t\tc = str(input())\n\t\tfor j in range(m):\n\t\t\tpic[i][j] = c[j]\n\tnew = [[0] * (m + 2) for i in range(n + 1)]\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif pic[i][j] == '*':\n\t\t\t\tnew[i][j + 1] = min(new[i + 1][j], new[i + 1][j + 1], new[i + 1][j + 2]) + 1\n\tk = 0\n\tfor i in range(n + 1):\n\t\tfor j in range(m + 2):\n\t\t\tk += new[i][j]\n\tprint(k)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tdict = []\n\tk = 0\n\tfor i in range(n):\n\t\tdict.append(i)\n\t\tdict[i] = []\n\t\ta = list(input())\n\t\tfor j in range(m):\n\t\t\tif a[j] == '*':\n\t\t\t\tk = k + 1\n\t\t\t\tdict[i].append(k)\n\t\t\telse:\n\t\t\t\tdict[i].append(0)\n\tfor i in range(0, n - 1):\n\t\tfor j in range(1, m - 1):\n\t\t\tp = dict[i][j]\n\t\t\tif dict[i][j] != 0:\n\t\t\t\tx = i + 1\n\t\t\t\ta = 1\n\t\t\t\tb = 2\n\t\t\t\twhile x < n and j + a < m:\n\t\t\t\t\tif dict[x][j + a] - dict[x][j - a] == b:\n\t\t\t\t\t\tk = k + 1\n\t\t\t\t\t\tx = x + 1\n\t\t\t\t\t\ta = a + 1\n\t\t\t\t\t\tb = b + 2\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\tprint(k)\n", "n = int(input())\nfor i in range(n):\n\t(p, q) = [int(x) for x in input().split()]\n\ttree = []\n\tfor j in range(p):\n\t\ttree.append([1 if x == '*' else 0 for x in list(input())])\n\tfor x in range(p - 2, -1, -1):\n\t\tfor y in range(q):\n\t\t\tif x + 1 < p and y - 1 < q and (y + 1 < q) and (x + 1 >= 0) and (y - 1 >= 0) and (y + 1 >= 0):\n\t\t\t\ttree[x][y] = tree[x][y] + tree[x][y] * min(tree[x + 1][y - 1], tree[x + 1][y], tree[x + 1][y + 1])\n\tprint(sum(map(sum, tree)))\n", "T = int(input())\nfor t in range(T):\n\t(n, m) = list(map(int, input().split()))\n\tmatrix = []\n\tans = []\n\tfor i in range(n):\n\t\tmatrix.append(list(input()))\n\t\tans.append([0] * m)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif matrix[i][j] == '*':\n\t\t\t\tans[i][j] = 1\n\tfor i in range(n - 2, -1, -1):\n\t\tfor j in range(1, m - 1):\n\t\t\tif matrix[i][j] == '*':\n\t\t\t\tans[i][j] = min(ans[i + 1][j], ans[i + 1][j - 1], ans[i + 1][j + 1]) + 1\n\tmainans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tmainans += ans[i][j]\n\tprint(mainans)\n", "import sys\nt = int(input())\nfor test in range(t):\n\t[n, m] = list(map(int, input().split(' ')))\n\ta = []\n\tfor i in range(n):\n\t\ta.append(input())\n\tres = 0\n\tb = []\n\tfor i in range(n):\n\t\tk = 0\n\t\tbi = []\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tbi.append(1)\n\t\t\t\tk += 1\n\t\t\t\tfor x in range(1, (k + 1) // 2):\n\t\t\t\t\tbi[j - x] += 1\n\t\t\telse:\n\t\t\t\tbi.append(0)\n\t\t\t\tk = 0\n\t\tb.append(bi)\n\tfor j in range(m):\n\t\tif b[0][j] > 0:\n\t\t\tres += 1\n\tfor i in range(1, n):\n\t\tfor j in range(m):\n\t\t\tres = res + min(b[i][j], b[i - 1][j] + 1, i + 1)\n\t\t\tb[i][j] = min(b[i][j], b[i - 1][j] + 1, i + 1)\n\tprint(res)\n", "for i in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tl = []\n\tfor i in range(n):\n\t\ta = input()\n\t\ts = [0] * m\n\t\tfor i in range(len(a)):\n\t\t\tif a[i] == '*':\n\t\t\t\ts[i] = 1\n\t\tl.append(s)\n\tfor i in range(n):\n\t\tl[i].insert(0, 0)\n\tfor i in range(n):\n\t\tfor j in range(1, m + 1):\n\t\t\tif l[i][j]:\n\t\t\t\tl[i][j] += l[i][j - 1]\n\tstar = 0\n\tfor i in range(n):\n\t\tfor j in range(1, m + 1):\n\t\t\tc = 0\n\t\t\tfor k in range(0, n):\n\t\t\t\tif 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):\n\t\t\t\t\tc += 1\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tstar += c\n\tprint(star)\n", "t = int(input())\nfor q in range(t):\n\t(n, m) = map(int, input().split())\n\ta = n * [0]\n\tfor w in range(n):\n\t\ta[w] = input()\n\tdp = [[0 for i in range(m)] for j in range(n)]\n\tfor i in list(reversed(range(n))):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '.':\n\t\t\t\tdp[i][j] = 0\n\t\t\telif j > 0 and j < m - 1 and (i < n - 1):\n\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\telse:\n\t\t\t\tdp[i][j] = 1\n\ts = 0\n\tfor i in dp:\n\t\ts += sum(i)\n\tprint(s)\n", "def main():\n\tfor _ in range(int(input())):\n\t\t(n, m) = map(int, input().split())\n\t\tmm = []\n\t\tans = 0\n\t\tfor i in range(n):\n\t\t\ts = input()\n\t\t\tl = []\n\t\t\tfor j in s:\n\t\t\t\tif j == '.':\n\t\t\t\t\tl.append(0)\n\t\t\t\telse:\n\t\t\t\t\tl.append(1)\n\t\t\tmm.append(l)\n\t\tfor i in range(n - 1, -1, -1):\n\t\t\tif i - 1 >= 0:\n\t\t\t\tfor j in range(1, m - 1):\n\t\t\t\t\tif mm[i][j] > 0 and mm[i - 1][j] > 0:\n\t\t\t\t\t\tif mm[i][j - 1] > 0 and mm[i][j + 1] > 0:\n\t\t\t\t\t\t\tmm[i - 1][j] += min(mm[i][j - 1], mm[i][j + 1])\n\t\tans = 0\n\t\tfor l in mm:\n\t\t\tans += sum(l)\n\t\tprint(ans)\nmain()\n", "from collections import deque\nfrom pprint import pprint\nt = int(input())\nfor _ in range(t):\n\t(n, m) = list(map(int, input().split()))\n\tq = deque()\n\tmat = [0 for i in range(n)]\n\tv = [[0] * m for i in range(n)]\n\tfor i in range(n):\n\t\tmat[i] = list(input())\n\tfirst = False\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] == '.':\n\t\t\t\tq.append((i, j, 0))\n\t\t\t\tfirst = first or i == 0\n\t\t\t\tv[i][j] = 1\n\t\t\t\tmat[i][j] = 0\n\tif len(q) == 0 or not first:\n\t\tq.append((0, 0, 1))\n\t\tv[0][0] = 1\n\t\tmat[0][0] = 1\n\twhile q:\n\t\t(r, c, dist) = q.popleft()\n\t\tfor (row, col) in [(r + 1, c), (r, c - 1), (r, c + 1)]:\n\t\t\tif 0 <= row < n and 0 <= col < m:\n\t\t\t\tif not v[row][col]:\n\t\t\t\t\tmat[row][col] = min(col + 1, row + 1, m - col, dist + 1)\n\t\t\t\t\tq.append((row, col, dist + 1))\n\t\t\t\t\tv[row][col] = 1\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tans += mat[i][j]\n\tprint(ans)\n", "def solve():\n\t(n, m) = map(int, input().split())\n\ta = []\n\tdp = []\n\tfor i in range(n):\n\t\ta.append([''] * m)\n\t\tdp.append([0] * m)\n\tfor i in range(n):\n\t\ts = input()\n\t\tfor j in range(m):\n\t\t\ta[n - i - 1][j] = s[j]\n\tfor i in range(m):\n\t\tif a[0][i] == '*':\n\t\t\tdp[0][i] = 1\n\t\telse:\n\t\t\tdp[0][i] = 0\n\tfor i in range(1, n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tdp[i][j] = 1\n\t\t\t\tif j > 0 and j < m - 1:\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])\n\t\t\telse:\n\t\t\t\tdp[i][j] = 0\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tans += dp[i][j]\n\tprint(ans)\ntests = int(input())\nwhile tests > 0:\n\tsolve()\n\ttests = tests - 1\n", "from bisect import *\nfrom collections import *\nfrom math import gcd, ceil, sqrt, floor, inf\nfrom heapq import *\nfrom itertools import *\nfrom operator import add, mul, sub, xor, truediv, floordiv\nfrom functools import *\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef RL():\n\treturn map(int, sys.stdin.readline().rstrip().split())\n\ndef RLL():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef N():\n\treturn int(input())\nfrom types import GeneratorType\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\nfarr = [1]\nifa = []\n\ndef fact(x, mod=0):\n\tif mod:\n\t\twhile x >= len(farr):\n\t\t\tfarr.append(farr[-1] * len(farr) % mod)\n\telse:\n\t\twhile x >= len(farr):\n\t\t\tfarr.append(farr[-1] * len(farr))\n\treturn farr[x]\n\ndef ifact(x, mod):\n\tglobal ifa\n\tifa.append(pow(farr[-1], mod - 2, mod))\n\tfor i in range(x, 0, -1):\n\t\tifa.append(ifa[-1] * i % mod)\n\tifa = ifa[::-1]\n\ndef per(i, j, mod=0):\n\tif i < j:\n\t\treturn 0\n\tif not mod:\n\t\treturn fact(i) // fact(i - j)\n\treturn farr[i] * ifa[i - j] % mod\n\ndef com(i, j, mod=0):\n\tif i < j:\n\t\treturn 0\n\tif not mod:\n\t\treturn per(i, j) // fact(j)\n\treturn per(i, j, mod) * ifa[j] % mod\n\ndef catalan(n):\n\treturn com(2 * n, n) // (n + 1)\n\ndef isprime(n):\n\tfor i in range(2, int(n ** 0.5) + 1):\n\t\tif n % i == 0:\n\t\t\treturn False\n\treturn True\n\ndef lowbit(n):\n\treturn n & -n\n\ndef inverse(a, m):\n\ta %= m\n\tif a <= 1:\n\t\treturn a\n\treturn (1 - inverse(m, a) * m) // a % m\n\nclass BIT:\n\n\tdef __init__(self, arr):\n\t\tself.arr = arr\n\t\tself.n = len(arr) - 1\n\n\tdef update(self, x, v):\n\t\twhile x <= self.n:\n\t\t\tself.arr[x] += v\n\t\t\tx += x & -x\n\n\tdef query(self, x):\n\t\tans = 0\n\t\twhile x:\n\t\t\tans += self.arr[x]\n\t\t\tx &= x - 1\n\t\treturn ans\n\nclass DSU:\n\n\tdef __init__(self, n):\n\t\tself.c = [-1] * n\n\n\tdef same(self, x, y):\n\t\treturn self.find(x) == self.find(y)\n\n\tdef find(self, x):\n\t\tif self.c[x] < 0:\n\t\t\treturn x\n\t\tself.c[x] = self.find(self.c[x])\n\t\treturn self.c[x]\n\n\tdef union(self, u, v):\n\t\t(u, v) = (self.find(u), self.find(v))\n\t\tif u == v:\n\t\t\treturn False\n\t\tif self.c[u] < self.c[v]:\n\t\t\t(u, v) = (v, u)\n\t\tself.c[u] += self.c[v]\n\t\tself.c[v] = u\n\t\treturn True\n\n\tdef size(self, x):\n\t\treturn -self.c[self.find(x)]\n\nclass UFS:\n\n\tdef __init__(self, n):\n\t\tself.parent = [i for i in range(n)]\n\t\tself.ranks = [0] * n\n\n\tdef find(self, x):\n\t\tif x != self.parent[x]:\n\t\t\tself.parent[x] = self.find(self.parent[x])\n\t\treturn self.parent[x]\n\n\tdef union(self, u, v):\n\t\t(pu, pv) = (self.find(u), self.find(v))\n\t\tif pu == pv:\n\t\t\treturn False\n\t\tif self.ranks[pu] >= self.ranks[pv]:\n\t\t\tself.parent[pv] = pu\n\t\t\tif self.ranks[pv] == self.ranks[pu]:\n\t\t\t\tself.ranks[pu] += 1\n\t\telse:\n\t\t\tself.parent[pu] = pv\n\ndef Prime(n):\n\tc = 0\n\tprime = []\n\tflag = [0] * (n + 1)\n\tfor i in range(2, n + 1):\n\t\tif not flag[i]:\n\t\t\tprime.append(i)\n\t\t\tc += 1\n\t\tfor j in range(c):\n\t\t\tif i * prime[j] > n:\n\t\t\t\tbreak\n\t\t\tflag[i * prime[j]] = prime[j]\n\t\t\tif i % prime[j] == 0:\n\t\t\t\tbreak\n\treturn flag\n\ndef dij(s, graph):\n\td = {}\n\td[s] = 0\n\theap = [(0, s)]\n\tseen = set()\n\twhile heap:\n\t\t(dis, u) = heappop(heap)\n\t\tif u in seen:\n\t\t\tcontinue\n\t\tseen.add(u)\n\t\tfor (v, w) in graph[u]:\n\t\t\tif v not in d or d[v] > d[u] + w:\n\t\t\t\td[v] = d[u] + w\n\t\t\t\theappush(heap, (d[v], v))\n\treturn d\n\ndef GP(it):\n\treturn [[ch, len(list(g))] for (ch, g) in groupby(it)]\n\nclass DLN:\n\n\tdef __init__(self, val):\n\t\tself.val = val\n\t\tself.pre = None\n\t\tself.next = None\n\ndef nb(i, j):\n\tfor (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:\n\t\tif 0 <= ni < n and 0 <= nj < m:\n\t\t\tyield (ni, nj)\n\n@bootstrap\ndef gdfs(r, p):\n\tif len(g[r]) == 1 and p != -1:\n\t\tyield None\n\tfor ch in g[r]:\n\t\tif ch != p:\n\t\t\tyield gdfs(ch, r)\n\tyield None\n\ndef f(x):\n\tfi = bisect_right(a, x)\n\tb = n - fi\n\tfor i in range(q):\n\t\tif k[i] > 0:\n\t\t\tif k[i] > x:\n\t\t\t\tb += 1\n\t\t\telse:\n\t\t\t\tfi += 1\n\t\telif -k[i] <= fi:\n\t\t\tfi -= 1\n\t\telse:\n\t\t\tb -= 1\n\treturn fi > 0\nt = N()\nfor i in range(t):\n\t(n, m) = RL()\n\ta = []\n\tfor i in range(n):\n\t\ta.append(input())\n\tans = 0\n\tb = [[0] for i in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tb[i].append(b[i][-1] + 1)\n\t\t\telse:\n\t\t\t\tb[i].append(b[i][-1])\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\ttmp = 1\n\t\t\t\tw = 1\n\t\t\t\tci = i\n\t\t\t\twhile i < n - 1 and j + w < m and (j - w >= 0):\n\t\t\t\t\tif b[i + 1][j + w + 1] - b[i + 1][j - w] == w * 2 + 1:\n\t\t\t\t\t\ttmp += 1\n\t\t\t\t\t\ti += 1\n\t\t\t\t\t\tw += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\ti = ci\n\t\t\t\tans += tmp\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(ROW, COL) = map(int, input().split())\n\tarr = []\n\tfor _ in range(ROW):\n\t\tarr.append(list(input()))\n\tsol = [[0 for i in range(COL)] for j in range(ROW)]\n\tfor row in range(ROW):\n\t\tfor col in range(COL):\n\t\t\tif arr[row][col] == '*':\n\t\t\t\tsol[row][col] = 1\n\tfor row in range(ROW - 2, -1, -1):\n\t\tfor col in range(COL):\n\t\t\tif col == 0 or col == COL - 1:\n\t\t\t\tpass\n\t\t\telif sol[row][col] >= 1:\n\t\t\t\tsol[row][col] += min(sol[row + 1][col - 1], sol[row + 1][col], sol[row + 1][col + 1])\n\tx = 0\n\tfor i in sol:\n\t\tx += sum(i)\n\tprint(x)\n", "t = int(input())\nwhile t > 0:\n\tt -= 1\n\t(n, m) = input().split()\n\t(n, m) = (int(n), int(m))\n\tmt = []\n\tfor i in range(n):\n\t\tmt.append(input())\n\tvst = []\n\tfor i in range(n):\n\t\tvst.append([0 for j in range(m)])\n\n\tdef fun(x, y):\n\t\tif mt[x][y] == '.':\n\t\t\treturn 0\n\t\telif not vst[x][y] == 0:\n\t\t\treturn vst[x][y]\n\t\telif x == n - 1 or y == m - 1 or y == 0:\n\t\t\tvst[x][y] = 1\n\t\t\treturn 1\n\t\telse:\n\t\t\top = min(fun(x + 1, y), fun(x + 1, y - 1), fun(x + 1, y + 1))\n\t\t\tif op == 0:\n\t\t\t\tvst[x][y] = 1\n\t\t\telse:\n\t\t\t\tvst[x][y] = op + 1\n\t\t\treturn vst[x][y]\n\tsm = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tsm += fun(i, j)\n\tprint(sm)\n", "for y in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tdp = []\n\tlst = []\n\tfor i in range(n):\n\t\tdp.append([0] * m)\n\t\tlst.append(list(input()))\n\tcnt = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif lst[i][j] == '*':\n\t\t\t\tif i == n - 1 or j == 0 or j == m - 1:\n\t\t\t\t\tdp[i][j] = 0\n\t\t\t\telif lst[i + 1][j - 1] == '*' and lst[i + 1][j] == '*' and (lst[i + 1][j + 1] == '*'):\n\t\t\t\t\tdp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j - 1]) + 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 0\n\t\t\t\tcnt += 1 + dp[i][j]\n\t\t\telse:\n\t\t\t\tpass\n\tprint(cnt)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ts = []\n\tkiri = [[0 for i in range(m)] for j in range(n)]\n\tkanan = [[0 for i in range(m)] for j in range(n)]\n\tfor i in range(n):\n\t\ts.append(list(map(lambda x: x == '*', input())))\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif j == 0:\n\t\t\t\tkiri[i][j] = 1\n\t\t\t\tif not s[i][j]:\n\t\t\t\t\tkiri[i][j] = 0\n\t\t\t\tcontinue\n\t\t\tif not s[i][j]:\n\t\t\t\tkiri[i][j] = 0\n\t\t\telse:\n\t\t\t\tkiri[i][j] = kiri[i][j - 1] + 1\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tif j == m - 1:\n\t\t\t\tkanan[i][j] = 1\n\t\t\t\tif not s[i][j]:\n\t\t\t\t\tkanan[i][j] = 0\n\t\t\t\tcontinue\n\t\t\tif not s[i][j]:\n\t\t\t\tkanan[i][j] = 0\n\t\t\telse:\n\t\t\t\tkanan[i][j] = kanan[i][j + 1] + 1\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif s[i][j]:\n\t\t\t\ttemp = 1\n\t\t\t\tfor k in range(i + 1, n):\n\t\t\t\t\tif kiri[k][j] - 1 >= k - i and kanan[k][j] - 1 >= k - i:\n\t\t\t\t\t\ttemp += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\tans += temp\n\tprint(ans)\n", "def solve_2(grid):\n\tn = len(grid)\n\tm = len(grid[0])\n\tcount = 0\n\tdp = [[0 for x in range(m)] for y in range(n)]\n\tfor i in range(m):\n\t\tif grid[n - 1][i] == '*':\n\t\t\tdp[n - 1][i] = 1\n\tfor j in range(n):\n\t\tif grid[j][m - 1] == '*':\n\t\t\tdp[j][m - 1] = 1\n\tfor i in range(n - 2, -1, -1):\n\t\tfor j in range(m - 2, -1, -1):\n\t\t\tif grid[i][j] == '.':\n\t\t\t\tdp[i][j] = 0\n\t\t\telse:\n\t\t\t\tdp[i][j] = 1\n\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\tdp[i][j] = dp[i][j] + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\tans = 0\n\tfor z in dp:\n\t\tans += sum(z)\n\tprint(ans)\nt = int(input())\nfor test in range(t):\n\t(n, m) = input().split()\n\tn = int(n)\n\tm = int(m)\n\tgrid = []\n\tfor i in range(n):\n\t\tch = input()\n\t\ttemp = []\n\t\tfor x in ch:\n\t\t\ttemp.append(x)\n\t\tgrid.append(temp)\n\tsolve_2(grid)\n", "for i in range(int(input())):\n\t(n, m) = list(map(int, input().split()))\n\tmatrix = []\n\tfor i in range(n):\n\t\tmatrix.append(input())\n\tans = [[0 for i in range(m)] for j in range(n)]\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif matrix[i][j] == '*':\n\t\t\t\tif j < m - 2 and i > 0:\n\t\t\t\t\tif matrix[i][j + 1] == matrix[i][j + 2] == matrix[i - 1][j + 1] == '*':\n\t\t\t\t\t\tans[i - 1][j + 1] += 1 + min(ans[i][j], ans[i][j + 1], ans[i][j + 2])\n\t\t\t\tans[i][j] += 1\n\ttotal = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\ttotal += ans[i][j]\n\tprint(total)\n", "import math\nfrom sys import stdin, stdout\ninput = stdin.readline\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tl = [[0] * m for i in range(n)]\n\tl1 = [[0] * m for i in range(n)]\n\tl2 = [[0] * m for i in range(n)]\n\tfor i in range(n):\n\t\ts = str(input())\n\t\tfor j in range(m):\n\t\t\tif s[j] == '*':\n\t\t\t\tl[i][j] = 1\n\t\t\t\tl1[i][j] = 1\n\t\t\t\tl2[i][j] = 1\n\tfor i in range(1, n):\n\t\tfor j in range(1, m):\n\t\t\tif l[i][j] == 1:\n\t\t\t\tl1[i][j] = min(l1[i - 1][j], l1[i][j - 1]) + 1\n\t\tfor j in range(m - 2, -1, -1):\n\t\t\tif l[i][j] == 1:\n\t\t\t\tl2[i][j] = min(l2[i][j + 1], l2[i - 1][j]) + 1\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tans += min(l1[i][j], l2[i][j])\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tmat = []\n\tfor i in range(n):\n\t\ttemp = input()\n\t\tmat.append(temp)\n\tc = 0\n\tdp = [[0 for x in range(m)] for y in range(n)]\n\tfor i in range(n):\n\t\ttemp = 0\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] == '*':\n\t\t\t\ttemp += 1\n\t\t\tdp[i][j] = temp\n\n\tdef isvalid(x1, y1, x2, y2):\n\t\tif x1 < 0 or x1 >= n or y1 < 0 or (y1 >= m) or (y2 < 0) or (y2 >= m):\n\t\t\treturn False\n\t\treturn True\n\n\tdef allstars(x1, y1, x2, y2):\n\t\tif y1 == 0:\n\t\t\tif dp[x1][y2] == y2 - y1 + 1:\n\t\t\t\treturn True\n\t\t\telse:\n\t\t\t\treturn False\n\t\telif dp[x1][y2] - dp[x1][y1 - 1] == y2 - y1 + 1:\n\t\t\treturn True\n\t\treturn False\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] == '*':\n\t\t\t\tx1 = i\n\t\t\t\ty1 = j\n\t\t\t\tx2 = i\n\t\t\t\ty2 = j\n\t\t\t\twhile 1:\n\t\t\t\t\tif isvalid(x1, y1, x2, y2):\n\t\t\t\t\t\tif allstars(x1, y1, x2, y2):\n\t\t\t\t\t\t\tc += 1\n\t\t\t\t\t\t\tx1 += 1\n\t\t\t\t\t\t\ty1 -= 1\n\t\t\t\t\t\t\tx2 += 1\n\t\t\t\t\t\t\ty2 += 1\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\tprint(c)\n", "for _ in range(int(input())):\n\t(n, m) = list(map(int, input().split()))\n\ta = []\n\tfor i in range(n):\n\t\ta.append(input())\n\tans = [[0 for i in range(m)] for j in range(n)]\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tif j < m - 2 and i > 0:\n\t\t\t\t\tif a[i][j] == a[i - 1][j + 1] == a[i][j + 2] == a[i][j + 1] == '*':\n\t\t\t\t\t\tans[i - 1][j + 1] += 1 + min(ans[i][j], ans[i][j + 1], ans[i][j + 2])\n\t\t\t\tans[i][j] += 1\n\ttotal = 0\n\tfor i in range(n):\n\t\ttotal += sum(ans[i])\n\tprint(total)\n", "t = int(input())\nwhile t:\n\t(n, m) = map(int, input().split())\n\tli = []\n\tfor i in range(n):\n\t\tli.append(list(input()))\n\tdp = [[0 for i in range(m)] for j in range(n)]\n\tfor i in reversed(range(n)):\n\t\tfor j in reversed(range(m)):\n\t\t\tif li[i][j] == '*':\n\t\t\t\tif i + 1 < n and j - 1 >= 0 and (j + 1 < m):\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tans += dp[i][j]\n\tprint(ans)\n\tt -= 1\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = [input() for x in range(n)]\n\tans = 0\n\tfor j in range(m):\n\t\tw = 0\n\t\tfor i in range(n):\n\t\t\tw = min((w, j, m - j - 1))\n\t\t\tfor k in range(w + 1):\n\t\t\t\tif a[i][j + k] == '.' or a[i][j - k] == '.':\n\t\t\t\t\tw = k - 1\n\t\t\t\t\tbreak\n\t\t\tans += 1 + w\n\t\t\tw += 1\n\tprint(ans)\n", "def findTheSpruce(matrix):\n\ttotal = 0\n\tdp = [[0] * len(matrix[0]) for _ in range(len(matrix))]\n\tfor col in range(len(matrix[0])):\n\t\tdp[-1][col] = 1 if matrix[-1][col] == '*' else 0\n\t\ttotal += dp[-1][col]\n\tfor row in range(len(matrix) - 2, -1, -1):\n\t\tfor col in range(len(matrix[0])):\n\t\t\tif matrix[row][col] == '*':\n\t\t\t\tminimum = dp[row + 1][col]\n\t\t\t\tif col == 0:\n\t\t\t\t\tminimum = 0\n\t\t\t\telse:\n\t\t\t\t\tminimum = min(minimum, dp[row + 1][col - 1])\n\t\t\t\tif col == len(matrix[0]) - 1:\n\t\t\t\t\tminimum = 0\n\t\t\t\telse:\n\t\t\t\t\tminimum = min(minimum, dp[row + 1][col + 1])\n\t\t\t\tdp[row][col] = 1 + minimum\n\t\t\t\ttotal += dp[row][col]\n\treturn total\ntestcases = int(input().strip())\nfor _ in range(testcases):\n\t(n, m) = map(int, input().strip().split())\n\tmatrix = []\n\tfor i in range(n):\n\t\tmatrix.append(input().strip())\n\tprint(findTheSpruce(matrix))\n", "import sys\nimport os\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tarr = []\n\tfor i in range(n):\n\t\ts = input()\n\t\tarr.append(s)\n\tdp = [[0 for _ in range(m)] for _ in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif arr[i][j] == '*':\n\t\t\t\tdp[i][j] = dp[i][j - 1] + 1\n\t\t\telif j == 0:\n\t\t\t\tif arr[i][j] == '*':\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 0\n\t\t\telse:\n\t\t\t\tdp[i][j] = dp[i][j - 1]\n\tans = 0\n\tfor x in range(n):\n\t\tfor y in range(m):\n\t\t\tif arr[x][y] == '.':\n\t\t\t\tcontinue\n\t\t\tfor level in range(min(n - x, m - y, y + 1)):\n\t\t\t\tk = dp[x + level][y + level]\n\t\t\t\tif y - level - 1 < 0:\n\t\t\t\t\tk1 = 0\n\t\t\t\telse:\n\t\t\t\t\tk1 = dp[x + level][y - level - 1]\n\t\t\t\tif k - k1 != level * 2 + 1:\n\t\t\t\t\tbreak\n\t\t\t\tans += 1\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tdp = [[0] * m for i in range(n)]\n\tans = 0\n\tleft = [[0] * m for i in range(n)]\n\tright = [[0] * m for i in range(n)]\n\tfor i in range(n):\n\t\tl = list(input())\n\t\ta.append(l)\n\t\tfor j in range(m):\n\t\t\tif l[j] == '*':\n\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\tleft[i][j] = left[i][j - 1] + 1\n\t\t\t\telse:\n\t\t\t\t\tleft[i][j] = 1\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tif l[j] == '*':\n\t\t\t\tif j + 1 < m:\n\t\t\t\t\tright[i][j] = right[i][j + 1] + 1\n\t\t\t\telse:\n\t\t\t\t\tright[i][j] = 1\n\tfor i in range(n):\n\t\tj = 0\n\t\tchetchik = 0\n\t\twhile j < m:\n\t\t\tif a[i][j] == '*':\n\t\t\t\tdp[i][j] = 1\n\t\t\t\t(lefts, rights) = (left[i][j], right[i][j])\n\t\t\t\tadd = 0\n\t\t\t\tif i - 1 >= 0:\n\t\t\t\t\tadd = dp[i - 1][j]\n\t\t\t\tif lefts != 1 and rights != 1:\n\t\t\t\t\tif min(lefts, rights) - 1 > add:\n\t\t\t\t\t\tdp[i][j] = add + 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tdp[i][j] = min(lefts, rights)\n\t\t\t\tans += dp[i][j]\n\t\t\tj += 1\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tt = []\n\tfor i in range(n):\n\t\ta.append(input())\n\t\tx = []\n\t\ts = 0\n\t\tfor j in a[i]:\n\t\t\tif j == '*':\n\t\t\t\ts += 1\n\t\t\tx.append(s)\n\t\tt.append(x)\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tk = 1\n\t\t\telse:\n\t\t\t\tcontinue\n\t\t\twhile k <= n - i:\n\t\t\t\tl = j - k + 1\n\t\t\t\th = j + k - 1\n\t\t\t\tf = i + k - 1\n\t\t\t\tif l >= 0 and h < m:\n\t\t\t\t\tif l == 0:\n\t\t\t\t\t\ts = t[f][h]\n\t\t\t\t\telse:\n\t\t\t\t\t\ts = t[f][h] - t[f][l - 1]\n\t\t\t\t\tif s == h - l + 1:\n\t\t\t\t\t\tk += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tans += k - 1\n\tprint(ans)\n", "import sys\nimport math\nfrom collections import defaultdict as ddict\nfrom collections import deque\nimport heapq\nfrom queue import Queue\nfrom copy import deepcopy\nfrom bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nimport os\nfast_inp = lambda : sys.stdin.readline().rstrip('\\n')\nread_l = lambda : fast_inp().split(' ')\nread_li = lambda : list(map(int, fast_inp().split(' ')))\nread_lf = lambda : list(map(float, fast_inp().split(' ')))\nread_i = lambda : int(fast_inp())\nread_f = lambda : float(fast_inp())\nread = lambda : fast_inp()\nDEBUG = True\n\ndef debug(**kwargs):\n\tif not DEBUG:\n\t\treturn\n\tprint('=' * 20)\n\tfor (k, v) in kwargs.items():\n\t\tprint(f'\\t{k}:{v}\\t')\n\tprint('=' * 20)\n\ndef print_mat(mat):\n\tfor row in mat:\n\t\tprint(*row)\n\ndef solve() -> None:\n\t(n, m) = read_li()\n\tmatrix = [list(read()) for x in range(n)]\n\tdp = []\n\tfor i in range(n):\n\t\tdp.append([0] * m)\n\tcnt = 0\n\tfor i in range(n)[::-1]:\n\t\tfor j in range(m)[::-1]:\n\t\t\tif matrix[i][j] == '*':\n\t\t\t\tdp[i][j] = 1\n\t\t\t\tif not (i + 1 >= n or j - 1 < 0 or j + 1 >= m):\n\t\t\t\t\t(f1, f2, f3) = (dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])\n\t\t\t\t\tmn = min(f1, f2, f3)\n\t\t\t\t\tdp[i][j] += mn\n\t\t\t\tcnt += dp[i][j]\n\tprint(cnt)\nt = read_i()\nfor _ in range(t):\n\tsolve()\n", "t = int(input())\nwhile t > 0:\n\t(n, m) = map(int, input().split())\n\tdp = [[0] * m for i in range(n)]\n\tmatric = [input() for i in range(n)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif matric[i][j] == '*':\n\t\t\t\tif not (i == n - 1 or j == 0 or j == m - 1):\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j + 1], dp[i + 1][j - 1], dp[i + 1][j])\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\tans += dp[i][j]\n\tprint(ans)\n\tt -= 1\n", "t = int(input())\nfor _t in range(t):\n\t(n, m) = map(int, input().split())\n\tgrid = []\n\tfor i in range(n):\n\t\tgrid.append(input())\n\tdp = [[0 for i in range(m)] for j in range(n)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif grid[i][j] == '*':\n\t\t\t\tif i == n - 1 or j == 0 or j == m - 1:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\telse:\n\t\t\t\tdp[i][j] = 0\n\t\t\tans += dp[i][j]\n\tprint(ans)\n", "import sys\nimport math, bisect, operator\n(inf, m) = (float('inf'), 10 ** 9 + 7)\nsys.setrecursionlimit(10 ** 6)\nfrom itertools import groupby, accumulate\nfrom heapq import heapify, heappop, heappush\nfrom collections import deque, Counter, defaultdict\nI = lambda : int(sys.stdin.readline())\nneo = lambda : map(int, sys.stdin.readline().split())\nNeo = lambda : list(map(int, sys.stdin.readline().split()))\nfor _ in range(I()):\n\t(n, m) = neo()\n\tA = [input() for i in range(n)]\n\tdp = [[0] * m for j in range(n)]\n\tAns = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif A[i][j] == '*':\n\t\t\t\tdp[i][j] = 1\n\t\t\t\tif i + 1 < n and j - 1 > -1 and (j + 1 < m):\n\t\t\t\t\tdp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1\n\t\t\tAns += dp[i][j]\n\tprint(Ans)\n", "from sys import stdin, stdout\n\ndef INI():\n\treturn int(stdin.readline())\n\ndef INL():\n\treturn [int(_) for _ in stdin.readline().split()]\n\ndef INS():\n\treturn stdin.readline()\n\ndef MOD():\n\treturn pow(10, 9) + 7\n\ndef OPS(ans):\n\tstdout.write(str(ans) + '\\n')\n\ndef OPL(ans):\n\t[stdout.write(str(_) + ' ') for _ in ans]\n\tstdout.write('\\n')\nfor _ in range(INI()):\n\t(n, m) = INL()\n\tX = []\n\tfor _ in range(n):\n\t\tX.append(list(input()))\n\tD = [[0 for _ in range(m)] for _ in range(n)]\n\tfor _ in range(n - 1, -1, -1):\n\t\tfor __ in range(m - 1, -1, -1):\n\t\t\tif _ + 1 < n and __ + 1 < m and (-1 < __ - 1) and (X[_][__] == '*'):\n\t\t\t\tD[_][__] = min(D[_ + 1][__ - 1], D[_ + 1][__], D[_ + 1][__ + 1]) + 1\n\t\t\telif X[_][__] == '*':\n\t\t\t\tD[_][__] = 1\n\tans = 0\n\tfor _ in range(n):\n\t\tans += sum(D[_])\n\tOPS(ans)\n", "def checkStar(char):\n\tif char == '.':\n\t\treturn 0\n\telse:\n\t\treturn 1\nmatrix = list()\nfor t in [0] * int(input()):\n\t(n, m) = map(int, input().split())\n\tmatrix = [input() for _ in [0] * n]\n\tfor i in range(n):\n\t\tmatrix[i] = list(map(checkStar, matrix[i]))\n\tfor i in range(n - 1, 0, -1):\n\t\tfor j in range(1, m - 1):\n\t\t\tif matrix[i][j - 1] != 0 and matrix[i][j] != 0 and (matrix[i][j + 1] != 0) and (matrix[i - 1][j] != 0):\n\t\t\t\tmatrix[i - 1][j] += min(matrix[i][j - 1], matrix[i][j], matrix[i][j + 1])\n\tcount = sum([sum(i) for i in matrix])\n\tprint(count)\n", "import sys\nt = int(input())\nfor i in range(t):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor j in range(n):\n\t\ta.append(sys.stdin.readline().strip())\n\tdp = [[0 for j in range(m)] for k in range(n)]\n\ts = 0\n\tfor j in range(n):\n\t\tfor k in range(m):\n\t\t\tif a[j][k] == '*':\n\t\t\t\tif j > 0 and k > 1:\n\t\t\t\t\tdp[j][k] = 1 + min(dp[j - 1][k - 1], dp[j][k - 1], dp[j][k - 2])\n\t\t\t\telse:\n\t\t\t\t\tdp[j][k] = 1\n\t\t\ts = s + dp[j][k]\n\tprint(s)\n", "import sys, time\n\ndef get_ints():\n\treturn map(int, sys.stdin.readline().strip().split())\n\ndef get_int():\n\treturn int(sys.stdin.readline())\n\ndef get_line():\n\treturn sys.stdin.readline().strip()\n\ndef find(mat):\n\tcount = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tif mat[i][j] == '.':\n\t\t\t\tmat[i][j] = 0\n\t\t\telif j == 0 or j == m - 1 or i == n - 1:\n\t\t\t\tmat[i][j] = 1\n\t\t\telse:\n\t\t\t\tmin_val = min(mat[i + 1][j - 1], mat[i + 1][j], mat[i + 1][j + 1])\n\t\t\t\tmat[i][j] = min_val + 1\n\t\t\tcount += mat[i][j]\n\treturn count\nres = []\nfor _ in range(get_int()):\n\t(n, m) = get_ints()\n\tmat = []\n\tfor i in range(n):\n\t\tmat.append(list(get_line()))\n\tres.append(str(find(mat)))\nsys.stdout.write('\\n'.join(res))\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ts = [input() for i in range(n)]\n\ta = [[0] * m for i in range(n)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif s[i][j] == '*':\n\t\t\t\ta[i][j] = 1\n\t\t\t\tif i < n - 1 and j < m - 1 and (j > 0):\n\t\t\t\t\tif s[i + 1][j] == '*' and s[i + 1][j + 1] == '*' and (s[i + 1][j - 1] == '*'):\n\t\t\t\t\t\ta[i][j] += min([a[i + 1][j + 1], a[i + 1][j], a[i + 1][j - 1]])\n\t\t\tans += a[i][j]\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\ta = [[*input()] for _ in range(n)]\n\tans = 0\n\tl = [[0] * m for _ in range(n)]\n\tr = [[0] * m for _ in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tl[i][j] = 1 if a[i][j] == '*' else 0\n\t\t\tr[i][j] = 1 if a[i][j] == '*' else 0\n\tfor i in range(n):\n\t\tfor j in range(1, m):\n\t\t\tif l[i][j]:\n\t\t\t\tl[i][j] += l[i][j - 1]\n\tfor i in range(n):\n\t\tfor j in range(m - 2, -1, -1):\n\t\t\tif r[i][j]:\n\t\t\t\tr[i][j] += r[i][j + 1]\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tnx = 1\n\t\t\tif l[i][j]:\n\t\t\t\tfor k in range(i, n):\n\t\t\t\t\tif l[k][j] - 1 >= nx // 2 and r[k][j] - 1 >= nx // 2:\n\t\t\t\t\t\tans += 1\n\t\t\t\t\t\tnx += 2\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tl = []\n\tfor i in range(n):\n\t\tl.append(input())\n\tdp = [[0 for i in range(m + 1)] for i in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif l[i][j] == '*':\n\t\t\t\tdp[i][j + 1] = 1 + dp[i][j]\n\t\t\telse:\n\t\t\t\tdp[i][j + 1] = dp[i][j]\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tc = 1\n\t\t\td = 0\n\t\t\tfor b in range(i, n):\n\t\t\t\t(x, y) = (j - d, j + d)\n\t\t\t\tif x >= 0 and y <= m - 1:\n\t\t\t\t\tif dp[b][y + 1] - dp[b][x] == c:\n\t\t\t\t\t\tans += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\t\tc += 2\n\t\t\t\td += 1\n\tprint(ans)\n", "import sys\nm = {'*': 1, '.': 0}\n\ndef sip():\n\treturn sys.stdin.readline().rstrip()\n\ndef gen_test_cases():\n\tnum_tests = int(sip())\n\tfor i in range(num_tests):\n\t\t(height, width) = map(int, sip().split(' '))\n\t\tarr = [[m[c] for c in line] for line in [sys.stdin.readline().rstrip() for x in range(height)]]\n\t\tyield (height, width, arr)\nfor (h, w, mc) in gen_test_cases():\n\tfor y in range(1, h):\n\t\tfor x in range(1, w - 1):\n\t\t\tif mc[y][x] != 0:\n\t\t\t\tr = min(mc[y][x - 1], mc[y - 1][x])\n\t\t\t\tif r:\n\t\t\t\t\tmc[y][x] = r + 1\n\t\tfor x in reversed(range(w - 1)):\n\t\t\tif mc[y][x] != 0:\n\t\t\t\tmc[y][x] = min(mc[y][x], mc[y][x + 1] + 1)\n\tcount = sum([sum(mc[y]) for y in range(h)])\n\tprint(count)\n", "def solve():\n\t(n, m) = map(int, input().split())\n\ts = [str(input()) for i in range(n)]\n\tdp = [[0 for j in range(m)] for i in range(n)]\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(0, m):\n\t\t\tif s[i][j] == '*':\n\t\t\t\tif j == 0 or j == m - 1 or i == n - 1:\n\t\t\t\t\tdp[i][j] = 1\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1\n\tprint(sum([sum(dp[i]) for i in range(n)]))\nfor tt in range(int(input())):\n\tsolve()\n", "def count_spruce(mat):\n\tans = 0\n\tdp = {}\n\tfor i in range(len(mat)):\n\t\tfor j in range(len(mat[i])):\n\t\t\tsize = spruceSize(mat, i, j, dp)\n\t\t\tans += dp[i, j]\n\treturn ans\n\ndef spruceSize(mat, i, j, dp):\n\tkey = (i, j)\n\tif key in dp:\n\t\treturn dp[key]\n\tif i >= len(mat) or j < 0 or j >= len(mat[i]):\n\t\tdp[key] = 0\n\t\treturn 0\n\tminchilddepth = float('inf')\n\tif mat[i][j] == '.':\n\t\tdp[key] = 0\n\t\treturn 0\n\tfor jj in range(j - 1, j + 2):\n\t\tminchilddepth = min(minchilddepth, spruceSize(mat, i + 1, jj, dp))\n\tdp[key] = 1 + minchilddepth\n\treturn dp[key]\nt = int(input())\nfor c in range(t):\n\tinp = str(input())\n\tcomps = inp.split()\n\tn = int(comps[0])\n\tm = int(comps[1])\n\tmat = []\n\tfor row in range(n):\n\t\tmat.append(str(input()))\n\tprint(count_spruce(mat))\n", "t = int(input())\nfor _ in range(0, t):\n\t(n, m) = map(int, input().split())\n\ta = []\n\tfor _ in range(0, n):\n\t\ta.append(input())\n\tml = [[0 for _ in range(m + 1)] for _ in range(n)]\n\tfor i in range(0, n):\n\t\tfor j in range(0, m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tml[i][j + 1] = ml[i][j] + 1\n\t\t\telse:\n\t\t\t\tml[i][j + 1] = 0\n\tans = 0\n\tfor i in range(0, n):\n\t\tfor j in range(0, m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tfor k in range(0, min(n - i, m - j)):\n\t\t\t\t\tif ml[i + k][j + k + 1] >= 2 * k + 1:\n\t\t\t\t\t\tans = ans + 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\tprint(ans)\n", "import math, sys\nfrom collections import defaultdict, deque\nimport bisect as bi\n\ndef yes():\n\tprint('YES')\n\ndef no():\n\tprint('NO')\n\ndef I():\n\treturn int(sys.stdin.readline())\n\ndef In():\n\treturn map(int, sys.stdin.readline().split())\n\ndef Sn():\n\treturn sys.stdin.readline().strip()\n\ndef dict(a):\n\td = {}\n\tfor x in a:\n\t\tif d.get(x, -1) != -1:\n\t\t\td[x] += 1\n\t\telse:\n\t\t\td[x] = 1\n\treturn d\n\ndef find_gt(a, x):\n\ti = bi.bisect_left(a, x)\n\tif i != len(a):\n\t\treturn i\n\telse:\n\t\treturn -1\n\ndef cal(r, p, q, l, cnt, n, m, dp, visit):\n\tif r >= len(l):\n\t\treturn\n\tif p < 0 or q >= m:\n\t\treturn\n\tflag = 0\n\tif p == 0:\n\t\tif dp[r][q] != q - p + 1:\n\t\t\tflag = 1\n\telif dp[r][q] - dp[r][p - 1] != q - p + 1:\n\t\tflag = 1\n\tif flag:\n\t\treturn\n\telse:\n\t\tcnt[0] += 1\n\t\tcal(r + 1, p - 1, q + 1, l, cnt, n, m, dp, visit)\n\ndef main():\n\ttry:\n\t\t(n, m) = In()\n\t\tl = []\n\t\tfor i in range(n):\n\t\t\tl.append(Sn())\n\t\tcnt = [0]\n\t\tdp = [[0 for i in range(m)] for j in range(n)]\n\t\tfor i in range(n):\n\t\t\tcn = 0\n\t\t\tfor j in range(m):\n\t\t\t\tif l[i][j] == '*':\n\t\t\t\t\tcn += 1\n\t\t\t\tdp[i][j] = cn\n\t\tanswer = 0\n\t\tfor x in range(n):\n\t\t\tfor y in range(m):\n\t\t\t\tif l[x][y] == '.':\n\t\t\t\t\tcontinue\n\t\t\t\tfor k in range(min(n - x, m - y, y + 1)):\n\t\t\t\t\tif y - k - 1 < 0:\n\t\t\t\t\t\ttest = 0\n\t\t\t\t\telse:\n\t\t\t\t\t\ttest = dp[x + k][y - k - 1]\n\t\t\t\t\tif dp[x + k][y + k] - test != 2 * k + 1:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tanswer += 1\n\t\tprint(answer)\n\texcept:\n\t\tpass\nM = 998244353\nP = 1000000007\nfor _ in range(I()):\n\tmain()\n", "def findSpruces(matrix, n, m):\n\tcounts = [[0] * (m + 2) for _ in range(n + 1)]\n\tfor x in range(1, n + 1):\n\t\tfor y in range(1, m + 1):\n\t\t\tif matrix[n - x][y - 1] != '*':\n\t\t\t\tcontinue\n\t\t\ta = counts[x - 1][y - 1]\n\t\t\tb = counts[x - 1][y]\n\t\t\tc = counts[x - 1][y + 1]\n\t\t\tcounts[x][y] = min(a, b, c) + 1\n\treturn sum([item for sublist in counts for item in sublist])\nt = int(input())\nfor _ in range(t):\n\t(n, m) = list(map(int, input().split()))\n\tmatrix = []\n\tfor _ in range(n):\n\t\tmatrix.append(input())\n\tprint(findSpruces(matrix, n, m))\n", "def f(x: int):\n\treturn x % 2 + x // 2\n\ndef find_spruce(n: int, m: int, field: list):\n\tres = 0\n\ttemp_field = [[0 for j in range(m)] for i in range(n)]\n\tfor j in range(m):\n\t\tif field[0][j] == '*':\n\t\t\ttemp_field[0][j] = 1\n\t\t\tres += temp_field[0][j]\n\tfor i in range(1, n):\n\t\tseq = 0\n\t\tfor j in range(m):\n\t\t\tif field[i][j] == '*':\n\t\t\t\tseq += 1\n\t\t\telse:\n\t\t\t\tseq = 0\n\t\t\t\tcontinue\n\t\t\tif temp_field[i - 1][j - 1] != 0 and seq >= 3 and (f(seq) - temp_field[i - 1][j - 1] >= 1):\n\t\t\t\ttemp_field[i][j] = temp_field[i - 1][j - 1] + 1\n\t\t\telif temp_field[i - 1][j - 1] != 0 and seq >= 3:\n\t\t\t\ttemp_field[i][j] = f(seq)\n\t\t\telse:\n\t\t\t\ttemp_field[i][j] = 1\n\t\t\tres += temp_field[i][j]\n\treturn res\nt = int(input())\nfor i in range(t):\n\t(n, m) = map(int, input().split(' '))\n\tfield = []\n\tfor j in range(n):\n\t\tfield.append(input())\n\tprint(find_spruce(n, m, field))\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor tests in range(t):\n\t(n, m) = map(int, input().split())\n\tTREE = [input().strip() for i in range(n)]\n\tDP = [[0] * (m + 2) for i in range(n + 2)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif TREE[i][j] == '*':\n\t\t\t\tDP[i][j] = 1\n\tfor k in range(1, 250):\n\t\tfor i in range(k, n):\n\t\t\tfor j in range(k, m - k):\n\t\t\t\tif k <= min(DP[i][j], DP[i][j - 1], DP[i][j + 1], DP[i - 1][j]):\n\t\t\t\t\tDP[i][j] = k + 1\n\tANS = 0\n\tfor dp in DP:\n\t\tANS += sum(dp)\n\tprint(ANS)\n", "def solve():\n\t(n, m) = map(int, input().split())\n\tmatrix = []\n\tvalue = [[0 for x in range(m)] for y in range(n)]\n\tfor q in range(n):\n\t\tmatrix.append(list(input()))\n\tanswer = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m):\n\t\t\tif matrix[i][j] != '*':\n\t\t\t\tcontinue\n\t\t\tcounter = 0\n\t\t\tanswer += 1\n\t\t\tif i + 1 < n:\n\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\tif matrix[i + 1][j - 1] == '*':\n\t\t\t\t\t\tcounter += 1\n\t\t\t\tif matrix[i + 1][j] == '*':\n\t\t\t\t\tcounter += 1\n\t\t\t\tif j + 1 < m:\n\t\t\t\t\tif matrix[i + 1][j + 1] == '*':\n\t\t\t\t\t\tcounter += 1\n\t\t\tanswer -= 1\n\t\t\tif counter == 3:\n\t\t\t\tmini = 100000000000000000000000000\n\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\tif matrix[i + 1][j - 1] == '*':\n\t\t\t\t\t\tmini = min(mini, value[i + 1][j - 1])\n\t\t\t\tif matrix[i + 1][j] == '*':\n\t\t\t\t\tmini = min(mini, value[i + 1][j])\n\t\t\t\tif j + 1 < m:\n\t\t\t\t\tif matrix[i + 1][j + 1] == '*':\n\t\t\t\t\t\tmini = min(mini, value[i + 1][j + 1])\n\t\t\t\tvalue[i][j] = mini + 1\n\t\t\telse:\n\t\t\t\tvalue[i][j] = 1\n\t\t\tanswer += value[i][j]\n\tprint(answer)\nfor _ in range(int(input())):\n\tsolve()\n", "from sys import stdin\nfrom collections import defaultdict, Counter\n\ndef iinput():\n\treturn int(stdin.readline())\n\ndef minput():\n\treturn map(int, stdin.readline().split())\n\ndef linput():\n\treturn list(map(int, stdin.readline().split()))\nt = iinput()\nwhile t:\n\tt -= 1\n\t(n, m) = minput()\n\tmat = []\n\tfor i in range(n):\n\t\tmat.append(list(input()))\n\tdp = [[0 for _ in range(m)] for __ in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif mat[i][j] == '*':\n\t\t\t\tdp[i][j] = 1\n\tfor i in range(n - 2, -1, -1):\n\t\tfor j in range(1, m - 1):\n\t\t\tif dp[i][j] == 1:\n\t\t\t\tdp[i][j] += min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\tspruce = 0\n\tfor i in range(n):\n\t\tspruce += sum(dp[i])\n\tprint(spruce)\n", "import sys\nimport math\n\ndef II():\n\treturn int(sys.stdin.readline())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef MI():\n\treturn map(int, sys.stdin.readline().split())\n\ndef SI():\n\treturn sys.stdin.readline().strip()\n\ndef FACT(n, mod):\n\ts = 1\n\tfacts = [1]\n\tfor i in range(1, n + 1):\n\t\ts *= i\n\t\ts %= mod\n\t\tfacts.append(s)\n\treturn facts[n]\n\ndef C(n, k, mod):\n\treturn FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod\nt = II()\nfor q in range(t):\n\t(n, m) = MI()\n\tl = []\n\tfor i in range(n):\n\t\tl.append(list(SI()))\n\tans = 0\n\tdp = [[0 for i in range(m)] for j in range(n)]\n\tle = [[0 for i in range(m)] for j in range(n)]\n\tri = [[0 for i in range(m)] for j in range(n)]\n\tfor i in range(n):\n\t\tcount = 0\n\t\tfor j in range(m):\n\t\t\tle[i][j] = count\n\t\t\tif l[i][j] == '*':\n\t\t\t\tdp[i][j] = 1\n\t\t\t\tcount += 1\n\t\t\t\tans += 1\n\t\t\telse:\n\t\t\t\tcount = 0\n\t\tcount = 0\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tri[i][j] = count\n\t\t\tif l[i][j] == '*':\n\t\t\t\tcount += 1\n\t\t\telse:\n\t\t\t\tcount = 0\n\tfor i in range(1, n):\n\t\tfor j in range(m):\n\t\t\tif l[i][j] == '*':\n\t\t\t\tx = le[i][j]\n\t\t\t\ty = ri[i][j]\n\t\t\t\tz = dp[i - 1][j]\n\t\t\t\tif z != 0 and min(x, y, (z - 1) // 2 + 1) != 0:\n\t\t\t\t\tans += (min(x, y, (z - 1) // 2 + 1) * 2 + 1) // 2\n\t\t\t\t\tdp[i][j] = min(x, y, (z - 1) // 2 + 1) * 2 + 1\n\tprint(ans)\n", "t = int(input())\nwhile t:\n\t(n, m) = map(int, input().split())\n\tx = []\n\tfor i in range(n):\n\t\ty = input()\n\t\tx.append(list(y))\n\tdp = []\n\tfor i in range(n):\n\t\tdp.append([0] * m)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif x[i][j] == '*':\n\t\t\t\tdp[i][j] = 1\n\tfor i in range(n - 2, -1, -1):\n\t\tfor j in range(m - 2, 0, -1):\n\t\t\tif dp[i][j] == 1:\n\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tans += dp[i][j]\n\tprint(ans)\n\tt = t - 1\n", "def find_the_spruce():\n\tfor _ in range(int(input())):\n\t\t(n, m) = list(map(int, input().split()))\n\t\tarr = [[x for x in input()] for _ in range(n)]\n\t\tans = [[0 for _ in range(m)] for _ in range(n)]\n\t\tfor i in range(m):\n\t\t\tans[n - 1][i] = 1 if arr[n - 1][i] == '*' else 0\n\t\tfor i in range(n - 2, -1, -1):\n\t\t\tfor j in range(m):\n\t\t\t\tans[i][j] += 1 if arr[i][j] == '*' else 0\n\t\t\t\tif 1 <= j < m - 1 and arr[i][j] == '*':\n\t\t\t\t\tmin_el = ans[i + 1][j - 1:j + 2]\n\t\t\t\t\tans[i][j] += min(min_el)\n\t\tans_2 = 0\n\t\tfor i in range(n):\n\t\t\tans_2 += sum(ans[i])\n\t\tprint(ans_2)\nfind_the_spruce()\n", "import sys, os, io\n\ndef rs():\n\treturn sys.stdin.readline().rstrip()\n\ndef ri():\n\treturn int(sys.stdin.readline())\n\ndef ria():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef ws(s):\n\tsys.stdout.write(s + '\\n')\n\ndef wi(n):\n\tsys.stdout.write(str(n) + '\\n')\n\ndef wia(a):\n\tsys.stdout.write(' '.join([str(x) for x in a]) + '\\n')\nimport math, datetime, functools, itertools, operator, bisect, fractions, statistics\nfrom collections import deque, defaultdict, OrderedDict, Counter\nfrom fractions import Fraction\nfrom decimal import Decimal\nfrom sys import stdout\nfrom heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest\n\ndef main():\n\tstarttime = datetime.datetime.now()\n\tif os.path.exists('input.txt'):\n\t\tsys.stdin = open('input.txt', 'r')\n\t\tsys.stdout = open('output.txt', 'w')\n\ttc = ri()\n\tfor _ in range(tc):\n\t\t(n, m) = ria()\n\t\tz = []\n\t\tans = 0\n\t\tpref = []\n\t\tsuff = []\n\t\tfor i in range(n):\n\t\t\tt = rs()\n\t\t\tps = []\n\t\t\tss = []\n\t\t\tz.append(t)\n\t\t\tc = 0\n\t\t\tfor j in range(m):\n\t\t\t\tif j - 1 < 0 or t[j - 1] == '.':\n\t\t\t\t\tc = 0\n\t\t\t\telse:\n\t\t\t\t\tc += 1\n\t\t\t\tps.append(c)\n\t\t\tc = 0\n\t\t\tfor j in range(m - 1, -1, -1):\n\t\t\t\tif j + 1 >= m or t[j + 1] == '.':\n\t\t\t\t\tc = 0\n\t\t\t\telse:\n\t\t\t\t\tc += 1\n\t\t\t\tss.append(c)\n\t\t\tss = ss[::-1]\n\t\t\tpref.append(ps)\n\t\t\tsuff.append(ss)\n\t\tfor i in range(n):\n\t\t\tfor j in range(m):\n\t\t\t\tif z[i][j] == '*':\n\t\t\t\t\tfor x in range(n - i):\n\t\t\t\t\t\tif z[i + x][j] == '.' or pref[i + x][j] < x or suff[i + x][j] < x:\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\tans += 1\n\t\twi(ans)\n\tendtime = datetime.datetime.now()\n\ttime = (endtime - starttime).total_seconds() * 1000\n\tif os.path.exists('input.txt'):\n\t\tprint('Time:', time, 'ms')\n\nclass FastReader(io.IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, fd, chunk_size=1024 * 8):\n\t\tself._fd = fd\n\t\tself._chunk_size = chunk_size\n\t\tself.buffer = io.BytesIO()\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self, size=-1):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\nclass FastWriter(io.IOBase):\n\n\tdef __init__(self, fd):\n\t\tself._fd = fd\n\t\tself.buffer = io.BytesIO()\n\t\tself.write = self.buffer.write\n\n\tdef flush(self):\n\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass FastStdin(io.IOBase):\n\n\tdef __init__(self, fd=0):\n\t\tself.buffer = FastReader(fd)\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\nclass FastStdout(io.IOBase):\n\n\tdef __init__(self, fd=1):\n\t\tself.buffer = FastWriter(fd)\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.flush = self.buffer.flush\nsys.stdin = FastStdin()\nsys.stdout = FastStdout()\nmain()\n", "import sys\ninput = sys.stdin.readline\nI = lambda : list(map(int, input().split()))\n(t,) = I()\nfor _ in range(t):\n\t(n, m) = I()\n\tar = [list(input().strip()) for i in range(n)]\n\tans = 0\n\tarr = [[0] * (m + 1) for i in range(n)]\n\tfor i in range(n):\n\t\tarr[i][0] = int(ar[i][0] == '*')\n\t\tfor j in range(1, m):\n\t\t\tarr[i][j] += (ar[i][j] == '*') + arr[i][j - 1]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif ar[i][j] == '*':\n\t\t\t\tans += 1\n\t\t\t\t(ci, cj) = (i + 1, j)\n\t\t\t\tx = 1\n\t\t\t\twhile ci < n:\n\t\t\t\t\tif j + x < m and j - x - 1 >= -1 and (arr[ci][j + x] - arr[ci][j - x - 1] == 2 * x + 1):\n\t\t\t\t\t\tci += 1\n\t\t\t\t\t\tans += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tx += 1\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tnum = [[] for _ in range(n)]\n\ttab = [[0 for _ in range(m)] for _ in range(n)]\n\tfor i in range(n):\n\t\ts = input()\n\t\tfor j in s:\n\t\t\tnum[i].append(j)\n\tco = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tlis = []\n\t\t\tc1 = 0\n\t\t\tif num[i][j] == '*':\n\t\t\t\tco += 1\n\t\t\tif i + 1 < n and num[i][j] == '*':\n\t\t\t\tif num[i + 1][j] == '*':\n\t\t\t\t\tlis.append(tab[i + 1][j])\n\t\t\t\t\tc1 += 1\n\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\tif num[i + 1][j - 1] == '*':\n\t\t\t\t\t\tlis.append(tab[i + 1][j - 1])\n\t\t\t\t\t\tc1 += 1\n\t\t\t\tif j + 1 < m:\n\t\t\t\t\tif num[i + 1][j + 1] == '*':\n\t\t\t\t\t\tlis.append(tab[i + 1][j + 1])\n\t\t\t\t\t\tc1 += 1\n\t\t\tif c1 == 3:\n\t\t\t\tco += 1\n\t\t\t\ttab[i][j] += 1\n\t\t\tif len(lis) == 3:\n\t\t\t\tlis.sort()\n\t\t\t\tco += lis[0]\n\t\t\t\ttab[i][j] += lis[0]\n\tprint(co)\n", "from itertools import accumulate\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\t(a, b) = map(int, input().split())\n\t\tt = []\n\t\tfor i in range(a):\n\t\t\tl = input()\n\t\t\tt.append(l)\n\t\tdp = [[0] * (b + 2) for i in range(a + 1)]\n\t\tans = 0\n\t\tfor i in range(a - 1, -1, -1):\n\t\t\tfor j in range(1, b + 1):\n\t\t\t\tif t[i][j - 1] == '*':\n\t\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\t\tans += dp[i][j]\n\t\tprint(ans)\nmain()\n", "from heapq import *\nimport typing\nimport sys\nimport math\nimport collections\nimport bisect\nimport itertools\nimport heapq\nimport decimal\nimport copy\nimport operator\nINF = 10 ** 20\nMOD = 10 ** 9 + 7\n\ndef ni():\n\treturn int(sys.stdin.readline())\n\ndef ns():\n\treturn map(int, sys.stdin.readline().split())\n\ndef na():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef na1():\n\treturn list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))\n\ndef main():\n\tt = ni()\n\tfor ti in range(t):\n\t\t(h, w) = ns()\n\t\tmat = [list(input()) for _ in range(h)]\n\t\tcnt = [[-1 for _ in range(w)] for __ in range(h)]\n\n\t\tdef dfs(y, x):\n\t\t\tif not (0 <= y < h and 0 <= x < w):\n\t\t\t\treturn\n\t\t\tif cnt[y][x] != -1:\n\t\t\t\treturn\n\t\t\tif mat[y][x] == '*':\n\t\t\t\tcnt[y][x] = 1\n\t\t\telse:\n\t\t\t\tcnt[y][x] = 0\n\t\t\t\treturn\n\t\t\tif 0 < x < w - 1:\n\t\t\t\tif y + 1 >= h:\n\t\t\t\t\treturn\n\t\t\t\tdfs(y + 1, x - 1)\n\t\t\t\tdfs(y + 1, x)\n\t\t\t\tdfs(y + 1, x + 1)\n\t\t\t\tcnt[y][x] += min(cnt[y + 1][x - 1], cnt[y + 1][x], cnt[y + 1][x + 1])\n\t\tfor i in range(h):\n\t\t\tfor j in range(w):\n\t\t\t\tdfs(i, j)\n\t\tans = sum([sum(c) for c in cnt])\n\t\tprint(ans)\nmain()\n", "for _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tl = []\n\tfa = []\n\tfor i in range(n):\n\t\ts = input()\n\t\tl.append(s)\n\t\tk = []\n\t\tfor i in range(m):\n\t\t\tk.append(0)\n\t\tfa.append(k)\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif l[i][j] == '*':\n\t\t\t\tf = 0\n\t\t\t\tx = j\n\t\t\t\ty = j\n\t\t\t\tsom = 0\n\t\t\t\twhile f == 0:\n\t\t\t\t\tif x > -1 and y < m:\n\t\t\t\t\t\tif l[i][x] == '*' and l[i][y] == '*':\n\t\t\t\t\t\t\tsom += 1\n\t\t\t\t\t\t\tx -= 1\n\t\t\t\t\t\t\ty += 1\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tf = 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tf = 1\n\t\t\t\tfa[i][j] = som\n\ti = 0\n\twhile i < n:\n\t\tj = 0\n\t\twhile j < m:\n\t\t\tif fa[i][j] > 0:\n\t\t\t\tx = i\n\t\t\t\tsom = 0\n\t\t\t\th = 1\n\t\t\t\twhile x < n:\n\t\t\t\t\tif fa[x][j] >= h:\n\t\t\t\t\t\tsom += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tx += 1\n\t\t\t\t\th += 1\n\t\t\t\tans += som\n\t\t\tj = j + 1\n\t\ti += 1\n\tprint(ans)\n", "t = int(input())\nfor _ in range(0, t):\n\tdp = {}\n\t(a, b) = map(int, input().split(' '))\n\tboard = []\n\tfor _ in range(a):\n\t\tboard.append(list(input()))\n\tanswer = 0\n\n\tdef heightSpruce(y, x):\n\t\tif board[y][x] == '.':\n\t\t\treturn 0\n\t\tif y == a - 1:\n\t\t\treturn 1\n\t\tif (y, x) in dp:\n\t\t\treturn dp[y, x]\n\t\tans = 1\n\t\tstartX = x - 1\n\t\tendX = x + 1\n\t\tif 0 <= startX and endX <= b - 1:\n\t\t\tminHeight = 1000\n\t\t\tminHeight = min(minHeight, heightSpruce(y + 1, startX))\n\t\t\tminHeight = min(minHeight, heightSpruce(y + 1, x))\n\t\t\tminHeight = min(minHeight, heightSpruce(y + 1, endX))\n\t\t\tans = 1 + minHeight\n\t\t\tdp[y, x] = ans\n\t\telse:\n\t\t\tdp[y, x] = ans\n\t\treturn dp[y, x]\n\tfor y in range(a):\n\t\tfor x in range(b):\n\t\t\th = heightSpruce(y, x)\n\t\t\tanswer += h\n\tprint(answer)\n", "import sys\ninput = lambda : sys.stdin.readline().rstrip()\n\ndef solve(n, m):\n\tL0 = []\n\tL1 = []\n\tnum = [0 for i in range(m * n)]\n\tfor i in range(n):\n\t\tgrid = input()\n\t\tfor j in range(m):\n\t\t\tif grid[j] == '*':\n\t\t\t\tc = i * m + j\n\t\t\t\tnum[c] = 1\n\t\t\t\tif i >= 1 and 1 <= j < m - 1:\n\t\t\t\t\tL1.append(c)\n\tk = 1\n\twhile L1:\n\t\tL0 = L1\n\t\tL1 = []\n\t\tfor c in L0:\n\t\t\tif min(num[c], num[c - m], num[c - 1], num[c + 1]) == k:\n\t\t\t\tnum[c] += 1\n\t\t\t\tL1.append(c)\n\t\tk += 1\n\treturn sum(num)\nt = int(input())\nfor i in range(t):\n\t(n, m) = map(int, input().split())\n\tprint(solve(n, m))\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tc = [input()[:-1] for i in range(n)]\n\tc = [[1 if j == '*' else 0 for j in ci] for ci in c]\n\tru = [[0] * (m + 1) for i in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tru[i][j + 1] = ru[i][j] + c[i][j]\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tfor k in range(n):\n\t\t\t\tif not i + k < n or j + k + 1 > m or j - k < 0:\n\t\t\t\t\tbreak\n\t\t\t\tif ru[i + k][j + k + 1] - ru[i + k][j - k] == 2 * k + 1:\n\t\t\t\t\tans += 1\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\tprint(ans)\n", "t = int(input())\ng = []\nfor x in range(t):\n\t(n, m) = input().split()\n\tl = []\n\tfor y in range(int(n)):\n\t\tl.append(input())\n\tp = [[0] * (int(m) + 2) for i in range(int(n) + 1)]\n\tfor i in range(int(n) - 1, -1, -1):\n\t\tfor j in range(1, int(m) + 1):\n\t\t\tif l[i][j - 1] == '*':\n\t\t\t\tp[i][j] = min(p[i + 1][j - 1], p[i + 1][j], p[i + 1][j + 1]) + 1\n\tprint(sum([sum(h) for h in p]))\n", "import sys, os\nimport math\nif os.path.exists('in.txt'):\n\tsys.stdin = open('in.txt', 'r')\nfrom io import BytesIO, IOBase\n\ndef main():\n\tpass\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef MI():\n\treturn map(int, input().split())\n\ndef out(var):\n\tsys.stdout.write(str(var) + '\\n')\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tinp = []\n\tout = 0\n\tfor i in range(n):\n\t\tinp.append(list(input()))\n\tmat = [[] for i in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tk = 0\n\t\t\twhile j - k >= 0 and j + k < m:\n\t\t\t\tif inp[i][j - k] == '*' and inp[i][j + k] == '*':\n\t\t\t\t\tk += 1\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tmat[i].append(k)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tk = 0\n\t\t\twhile i + k < n:\n\t\t\t\tif mat[i + k][j] >= k + 1:\n\t\t\t\t\tk += 1\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tout += k\n\tprint(out)\n", "import sys\nfrom itertools import accumulate\nimport os\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nT = int(input())\nfor _ in range(T):\n\t(r, c) = map(int, input().split())\n\tarr = [None] * r\n\tpref = [[0] * c for _ in range(r)]\n\tfor i in range(r):\n\t\tarr[i] = input()\n\t\tpref[i] = [1 if arr[i][j] == '*' else 0 for j in range(c)]\n\t\tpref[i] = list(accumulate(pref[i]))\n\tans = 0\n\tfor i in range(r):\n\t\tfor j in range(c):\n\t\t\tif arr[i][j] == '.':\n\t\t\t\tcontinue\n\t\t\tfor cur_row in range(i, r):\n\t\t\t\trelative_row = cur_row - i\n\t\t\t\t(left, right) = (j - relative_row, j + relative_row)\n\t\t\t\tif not 0 <= left < c or not 0 <= right < c:\n\t\t\t\t\tbreak\n\t\t\t\tstar_cnt = pref[cur_row][right] - (pref[cur_row][left - 1] if left - 1 >= 0 else 0)\n\t\t\t\tif star_cnt != right - left + 1:\n\t\t\t\t\tbreak\n\t\t\t\tans += 1\n\tprint(ans)\n", "(z, zz) = (input, lambda : list(map(int, z().split())))\nfast = lambda : stdin.readline().strip()\nzzz = lambda : [int(i) for i in fast().split()]\n(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))\nfrom string import *\nfrom re import *\nfrom collections import *\nfrom queue import *\nfrom sys import *\nfrom collections import *\nfrom math import *\nfrom heapq import *\nfrom itertools import *\nfrom bisect import *\nfrom collections import Counter as cc\nfrom math import factorial as f\nfrom bisect import bisect as bs\nfrom bisect import bisect_left as bsl\nfrom itertools import accumulate as ac\n\ndef lcd(xnum1, xnum2):\n\treturn xnum1 * xnum2 // gcd(xnum1, xnum2)\n\ndef prime(x):\n\tp = ceil(x ** 0.5) + 1\n\tfor i in range(2, p):\n\t\tif x % i == 0 and x != 2 or x == 0:\n\t\t\treturn 0\n\treturn 1\n\ndef dfs(u, visit, graph):\n\tvisit[u] = 1\n\tfor i in graph[u]:\n\t\tif not visit[i]:\n\t\t\tdfs(i, visit, graph)\n\ndef output(answer):\n\tstdout.write(str(answer))\nnum = int(fast())\nfor i in range(num):\n\t(n, m) = zzz()\n\tlst = []\n\tfor i in range(n):\n\t\tlst.append(fast())\n\tdp = [[0] * (m + 2) for i in range(n + 1)]\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tfor j in range(1, m + 1):\n\t\t\tif lst[i][j - 1] == '*':\n\t\t\t\tdp[i][j] = 1 + min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1])\n\t\t\tans += dp[i][j]\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = map(int, input().split())\n\tinp = []\n\tfor i in range(n):\n\t\ts = input()\n\t\tinp.append(s)\n\tans = 0\n\tR = []\n\tL = []\n\tfor i in range(n):\n\t\tlow = 0\n\t\thigh = 0\n\t\tright = []\n\t\tleft = []\n\t\twhile high < m:\n\t\t\tif inp[i][high] == '*':\n\t\t\t\twhile high < m and inp[i][high] == '*':\n\t\t\t\t\thigh += 1\n\t\t\t\tfor j in range(high - low):\n\t\t\t\t\tleft.append(j)\n\t\t\t\t\tright.append(high - low - j - 1)\n\t\t\t\tlow = high\n\t\t\telse:\n\t\t\t\tleft.append(0)\n\t\t\t\tright.append(0)\n\t\t\t\thigh += 1\n\t\t\t\tlow += 1\n\t\tR.append(right)\n\t\tL.append(left)\n\tmain = [[0 for i in range(m)]]\n\tfor i in range(n):\n\t\ttemp = []\n\t\tfor j in range(m):\n\t\t\tif inp[i][j] == '*':\n\t\t\t\tx = min(main[i][j] + 1, min(L[i][j], R[i][j]) + 1)\n\t\t\t\tans += x\n\t\t\t\ttemp.append(x)\n\t\t\telse:\n\t\t\t\ttemp.append(0)\n\t\tmain.append(temp)\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = [int(i) for i in input().split()]\n\tcnt = 0\n\ta = []\n\tdp = []\n\tfor i in range(n):\n\t\tdpp = []\n\t\tx = input()\n\t\ta.append(x)\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '*':\n\t\t\t\tdpp.append([1, 1])\n\t\t\telse:\n\t\t\t\tdpp.append([0, 0])\n\t\tdp.append(dpp)\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif a[i][j] == '.':\n\t\t\t\tcontinue\n\t\t\tif j != 0:\n\t\t\t\tdp[i][j][0] += dp[i][j - 1][0]\n\t\t\tcnt += 1\n\t\t\tif i != 0 and j != 0:\n\t\t\t\tfor kk in range(1, dp[i - 1][j - 1][1] + 1):\n\t\t\t\t\tif dp[i][j][0] >= 2 * kk + 1:\n\t\t\t\t\t\tcnt += 1\n\t\t\t\t\t\tdp[i][j][1] = kk + 1\n\tprint(cnt)\n", "t = int(input())\nml = []\nfor ind in range(t):\n\ts = input()\n\ts = s.split()\n\tfor i in range(len(s)):\n\t\ts[i] = int(s[i])\n\tn = s[0]\n\tm = s[1]\n\ta = []\n\tb = []\n\tfor ind in range(m + 2):\n\t\tb.append(0)\n\tfor ind in range(n + 2):\n\t\ta.append(b.copy())\n\tfor i in range(n):\n\t\ts2 = input()\n\t\tfor j in range(m):\n\t\t\tif s2[j] == '*':\n\t\t\t\ta[i + 1][j + 1] = -1\n\tml.append([n, m, a])\n\ndef f(a, x, y):\n\tif a[y + 1][x + 1] == -1:\n\t\ta[y + 1][x + 1] = 1 + min([a[y + 2][x], a[y + 2][x + 1], a[y + 2][x + 2]])\n\ndef sum(a):\n\ts = 0\n\tfor l in a:\n\t\tfor x in l:\n\t\t\ts = s + x\n\treturn s\n\ndef main():\n\tfor e in ml:\n\t\tn = e[0]\n\t\tm = e[1]\n\t\ta = e[2]\n\t\ty = n - 1\n\t\tx = 0\n\t\twhile y > -1:\n\t\t\twhile x < m:\n\t\t\t\tf(a, x, y)\n\t\t\t\tx = x + 1\n\t\t\tx = 0\n\t\t\ty = y - 1\n\t\tprint(sum(a))\nmain()\n", "from sys import stdin, stdout\n\ndef II():\n\treturn int(stdin.readline())\n\ndef SI():\n\treturn stdin.readline()[:-1]\n\ndef MI():\n\treturn map(int, stdin.readline().split())\n\ndef solve():\n\t(n, m) = MI()\n\tc = []\n\tl = [[0 for i in range(m)] for j in range(n)]\n\tr = [[0 for i in range(m)] for j in range(n)]\n\tfor i in range(n):\n\t\ts = SI()\n\t\tc.append(s)\n\t\t(lcnt, rcnt) = (0, 0)\n\t\tfor j in range(m):\n\t\t\tk = m - 1 - j\n\t\t\tif s[j] == '.':\n\t\t\t\tlcnt = 0\n\t\t\telse:\n\t\t\t\tl[i][j] = lcnt\n\t\t\t\tlcnt += 1\n\t\t\tif s[k] == '.':\n\t\t\t\trcnt = 0\n\t\t\telse:\n\t\t\t\tr[i][k] = rcnt\n\t\t\t\trcnt += 1\n\tans = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif c[i][j] == '.':\n\t\t\t\tcontinue\n\t\t\tans += 1\n\t\t\tfor h in range(1, n - i):\n\t\t\t\tif l[i + h][j] < h or r[i + h][j] < h:\n\t\t\t\t\tbreak\n\t\t\t\tans += 1\n\tstdout.write('{} \\n'.format(ans))\nt = II()\nfor _ in range(t):\n\tsolve()\n", "import sys\ninput = sys.stdin.readline\nfrom collections import defaultdict as dc\nfrom collections import Counter\nfrom bisect import bisect_right, bisect_left\nimport math\nfrom operator import itemgetter\nfrom heapq import heapify, heappop, heappush\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tl = []\n\tfor i in range(n):\n\t\tl.append(list(input()[:-1]))\n\tf = [[0 for j in range(m)] for i in range(n)]\n\tb = [[0 for j in range(m)] for i in range(n)]\n\tfor i in range(n):\n\t\tc = 0\n\t\tfor j in range(m):\n\t\t\tb[i][j] = c\n\t\t\tif l[i][j] == '*':\n\t\t\t\tc += 1\n\t\t\telse:\n\t\t\t\tc = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tc = 0\n\t\tfor j in range(m - 1, -1, -1):\n\t\t\tf[i][j] = c\n\t\t\tif l[i][j] == '*':\n\t\t\t\tc += 1\n\t\t\telse:\n\t\t\t\tc = 0\n\tp = 0\n\tfor i in range(n):\n\t\tfor j in range(m):\n\t\t\tif l[i][j] == '*':\n\t\t\t\tp += 1\n\t\t\t\ta = 1\n\t\t\t\tfor k in range(i + 1, n):\n\t\t\t\t\tif l[k][j] == '*' and b[k][j] >= a and (f[k][j] >= a):\n\t\t\t\t\t\tp += 1\n\t\t\t\t\t\ta += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\tprint(p)\n", "for _ in range(int(input())):\n\t(n, m) = list(map(int, input().split()))\n\tc = []\n\tfor _ in range(n):\n\t\tc.append(input())\n\tpt = [0] * m\n\tans = 0\n\tfor i in range(n):\n\t\tct = [0] * m\n\t\tj = 0\n\t\twhile j < m:\n\t\t\tif c[i][j] == '*':\n\t\t\t\tstart = j\n\t\t\t\twhile j < m and c[i][j] == '*':\n\t\t\t\t\tj += 1\n\t\t\t\tfor k in range(start, j):\n\t\t\t\t\tct[k] = min(pt[k] + 1, k + 1 - start, j - k)\n\t\t\tj += 1\n\t\tpt = ct.copy()\n\t\tans += sum(ct)\n\tprint(ans)\n"]

difficulty: MEDIUM

source: codeforces

raw_problem:
B. Find the Spruce

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

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.

Example

Input

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

Output

5
3
23
34

Note

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

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

question:
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:
 ![image](2.png) Now Rick wants to know how many spruces his $$$n \times m$$$ matrix contains. Help Rick solve this problem.

Input
Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$).
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 500$$$) — matrix size.
Next $$$n$$$ lines of each test case contain $$$m$$$ characters $$$c_{i, j}$$$ — matrix contents. It is guaranteed that $$$c_{i, j}$$$ is either a "." or an "*".
It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$500^2$$$ ($$$\sum n \cdot m \le 500^2$$$).

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

Example
Input
4
2 3
.*.
***
2 3
.*.
**.
4 5
.***.
*****
*****
*.*.*
5 7
..*.*..
.*****.
*******
.*****.
..*.*..

Output
5
3
23
34

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

tags: ['Dynamic programming', 'Implementation', 'Complete search']

skill_types: ['Dynamic programming', 'Complete search']

data_split: test