Read problems statements in English, Mandarin Chinese and Russian as well. 

Sherlock is stuck. There is a N X N grid in which some cells are empty (denoted by ‘.’), while some cells have rocks in them (denoted by ‘#’). Sherlock is on the South of the grid. He has to watch what is happening on the East of the grid. He can place a mirror at 45 degrees on an empty cell in the grid, so that he'll see what is happening on East side by reflection from the mirror.

But, if there's a rock in his line of sight, he won't be able to see what's happening on East side. For example, following image shows all possible cells in which he can place the mirror.

You have to tell Sherlock in how many possible cells he can place the mirror and see what's happening on East side.

------ Input ------ 

First line, T, the number of testcases. Each testcase will consist of N in one line. Next N lines each contain N characters.

------ Output ------ 

For each testcase, print the number of possible options where mirror can be placed to see on the East side.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 1000$
 
Note: Large input data. Use fast input/output.

Time limit for PYTH and PYTH 3.1.2 has been set 8s.

----- Sample Input 1 ------ 
2
3
#..
#..
#..
3
#.#
#.#
#.#
----- Sample Output 1 ------ 
6
0
----- explanation 1 ------ 
Example case 1. All places where rock are not there are valid positions.Example case 2. No valid positions.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
t = int(input())
while t != 0:
	n = int(input())
	p = 0
	m = []
	c = [0] * n
	r = [0] * n
	for i in range(n):
		m.append(input())
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if m[i][j] == '#':
				c[j] = 1
				r[i] = 1
			elif c[j] == 0 and r[i] == 0:
				p = p + 1
	print(p)
	t = t - 1


output = []
for _ in range(int(input())):
	N = int(input())
	grid = []
	for _ in range(N):
		grid.append(input())
	row = [[True for _ in range(N)] for _ in range(N)]
	col = [[True for _ in range(N)] for _ in range(N)]
	for i in range(N):
		for j in range(N - 1, -1, -1):
			if grid[i][j] == '#':
				row[i][j] = False
			elif j < N - 1:
				row[i][j] = row[i][j + 1]
	for j in range(N):
		for i in range(N - 1, -1, -1):
			if grid[i][j] == '#':
				col[i][j] = False
			elif i < N - 1:
				col[i][j] = col[i + 1][j]
	num = 0
	for i in range(N):
		for j in range(N):
			if row[i][j] and col[i][j]:
				num += 1
	output.append(num)
for o in output:
	print(o)


for _ in range(int(input())):
	n = int(input())
	q = [input() for i in range(n)]
	dp = [[1] * n for i in range(n)]
	for i in range(n):
		t = 1
		y = 1
		for j in range(n - 1, -1, -1):
			if q[i][j] == '#':
				t = 0
			if q[j][i] == '#':
				y = 0
			dp[i][j] = min(dp[i][j], t)
			dp[j][i] = min(dp[j][i], y)
	print(sum((sum(i) for i in dp)))


def solve():
	n = int(input())
	grd = []
	for i in range(n):
		grd.append(list(input()))
	for j in range(n):
		for i in range(n - 1, -1, -1):
			if grd[i][j] == '#':
				break
			grd[i][j] = 1
	ans = 0
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if grd[i][j] == '#':
				break
			if grd[i][j] == 1:
				ans += 1
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	grid = []
	for i in range(n):
		grid.append(list(input()))
	grid.append(['.'] * n)
	grid.reverse()
	count = 0
	for i in range(1, n + 1):
		temp = 0
		for j in range(n - 1, -1, -1):
			if grid[i][j] == '.' and grid[i - 1][j] == '.' and (temp == 0):
				count += 1
			elif grid[i][j] == '.' and grid[i - 1][j] == '#':
				grid[i][j] = '#'
			else:
				temp = 1
	print(count)


def grid(arr):
	N = len(arr)
	xPath = [[0 for j in range(N)] for i in range(N)]
	yPath = [[0 for j in range(N)] for i in range(N)]
	for i in range(N):
		j = N - 1
		while j >= 0:
			if arr[i][j] == '.':
				xPath[i][j] = xPath[i][j + 1] if j != N - 1 else 1
			else:
				xPath[i][j] = 0
			if arr[j][i] == '.':
				yPath[j][i] = yPath[j + 1][i] if j != N - 1 else 1
			else:
				yPath[j][1] = 0
			j -= 1
	count = 0
	for i in range(N):
		for j in range(N):
			if xPath[i][j] == 1 and yPath[i][j] == 1:
				count += 1
	return count
n = int(input())
values = []
for test in range(n):
	noe = int(input())
	arr = []
	for row in range(noe):
		r = list(input())
		arr.append(r)
	values.append(grid(arr))
for i in values:
	print(i)


for _ in range(int(input())):
	n = int(input())
	l = []
	c = 0
	for i in range(n):
		l.append(input())
	for j in range(n - 1, -1, -1):
		for i in range(n - 1, -1, -1):
			if l[i][j] != '#':
				if l[i][j + 1:].find('#') == -1:
					c += 1
			else:
				break
	print(c)


for _ in range(int(input())):
	v = []
	h = []
	m = []
	count = 0
	n = int(input())
	for i in range(n):
		m.append(input())
	for i in m:
		for j in range(n - 1, -1, -1):
			if i[j] == '#':
				h.append(j)
				break
		else:
			h.append(-1)
	for j in range(n):
		for i in range(n - 1, -1, -1):
			if m[i][j] == '#':
				v.append(i)
				break
		else:
			v.append(-1)
	for i in range(n):
		for j in range(n):
			if j > h[i] and i > v[j]:
				count += 1
	print(count)


def solve():
	n = int(input())
	mat = []
	for i in range(n):
		mat.append(list(input()))
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if mat[i][j] == '#':
				break
			mat[i][j] = 1
	ans = 0
	for j in range(n):
		for i in range(n - 1, -1, -1):
			if mat[i][j] == '#':
				break
			if mat[i][j] == 1:
				ans += 1
	print(ans)
for t in range(int(input())):
	solve()


T = int(input())
for t in range(T):
	N = int(input())
	A = []
	B = []
	for i in range(N):
		s = input()
		A.append(list(s))
		B.append(list(s))
	counter = 0
	for y in range(N - 1, -1, -1):
		x = N - 1
		not_filled = True
		while x >= 0 and not_filled:
			if A[y][x] == '#':
				for x1 in range(x - 1, -1, -1):
					B[y][x1] = '#'
				not_filled = False
			x -= 1
	for x in range(0, N):
		y = N - 1
		not_filled = True
		while y >= 0 and not_filled:
			if A[y][x] == '#':
				for y1 in range(y - 1, -1, -1):
					B[y1][x] = '#'
				not_filled = False
			y -= 1
	counter = 0
	for y in range(0, N):
		for x in range(0, N):
			if B[y][x] == '.':
				counter += 1
	print(counter)


for _ in range(int(input())):
	N = int(input())
	s = []
	v1 = []
	v2 = []
	for i in range(N):
		s.append(input())
		v1.append([1] * N)
		v2.append([1] * N)
		for j in range(N):
			if s[i][j] == '#':
				v1[i][j] = v2[i][j] = 0
	for i in range(N - 2, -1, -1):
		for j in range(N):
			v1[j][i] *= v1[j][i + 1]
			v2[i][j] *= v2[i + 1][j]
	ans = 0
	for i in range(N):
		for j in range(N):
			ans += v1[i][j] * v2[i][j]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(input())
	cnt = 0
	obst = [False] * n
	for i in range(n - 1, -1, -1):
		valid = True
		for j in range(n - 1, -1, -1):
			if arr[i][j] == '#':
				if valid:
					valid = False
				obst[j] = True
				continue
			elif obst[j] or valid == False:
				continue
			else:
				cnt += 1
	print(cnt)


t = int(input())
for k in range(t):
	n = int(input())
	s = []
	for k in range(n):
		helper = input()
		hj = []
		for c in helper:
			hj.append(c)
		s.append(hj)
	ans = 0
	blrows = {}
	for j in reversed(range(n)):
		flag = True
		for i in reversed(range(n)):
			if s[i][j] == '#':
				flag = False
				if i not in blrows:
					blrows[i] = 0
			elif flag:
				if i not in blrows:
					ans += 1
	print(ans)


def call(grid, n):
	c = 0
	dp1 = [[0] * n for i in range(n)]
	dp2 = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if grid[i][j] == '.':
				dp1[i][j] = 1
			else:
				break
	for j in range(n):
		for i in range(n - 1, -1, -1):
			if grid[i][j] == '.':
				dp2[i][j] = 1
			else:
				break
	for i in range(n):
		for j in range(n):
			if dp1[i][j] == dp2[i][j] == 1:
				c += 1
	return c
t = int(input())
while t > 0:
	n = int(input())
	i = 0
	grid = []
	while i < n:
		arr = list(input())
		grid.append(arr)
		i += 1
	print(call(grid, n))
	t -= 1


try:
	for _ in range(0, int(input())):
		n = int(input())
		a = []
		ans = 0
		for i in range(0, n):
			a.append(input())
		for j in range(n - 1, -1, -1):
			for i in range(n - 1, -1, -1):
				if a[i][j] != '#':
					if a[i][j + 1:].find('#') == -1:
						ans += 1
				else:
					break
		print(ans)
except:
	pass


for _ in range(int(input())):
	N = int(input())
	arr = []
	for i in range(N):
		arr.append([*input()])
	right = [[0] * N for i in range(N)]
	for i in range(N):
		for j in range(N - 1, -1, -1):
			if arr[i][j] != '#':
				right[i][j] = 1
			else:
				break
	x = 0
	final = [[0] * N for i in range(N)]
	for i in range(N):
		for j in range(N - 1, -1, -1):
			if arr[j][i] != '#':
				if right[j][i] == 1:
					x += 1
			else:
				break
	print(x)


for t in range(int(input())):
	N = int(input())
	matrix = []
	for i in range(N):
		matrix.append(input())
	count = 0
	hr = []
	vr = []
	for i in range(N):
		j = 0
		while j < N:
			if matrix[i][N - j - 1] == '#':
				hr.append(N - j - 1)
				break
			j += 1
		else:
			hr.append(N - j - 1)
	for i in range(N):
		j = 0
		while j < N:
			if matrix[N - j - 1][i] == '#':
				vr.append(N - j - 1)
				break
			j += 1
		else:
			vr.append(N - j - 1)
	x = 0
	for h in hr:
		i = N - 1
		while i > h:
			if vr[i] < x:
				count += 1
			i -= 1
		x += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	M = []
	for i in range(n):
		M.append(input())
	x = [[True for _ in range(n)] for _ in range(n)]
	y = [[True for _ in range(n)] for _ in range(n)]
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if M[i][j] == '#':
				x[i][j] = False
			elif j != n - 1:
				x[i][j] = x[i][j + 1]
	for j in range(n):
		for i in range(n - 1, -1, -1):
			if M[i][j] == '#':
				y[i][j] = False
			elif i != n - 1:
				y[i][j] = y[i + 1][j]
	ans = 0
	for i in range(n):
		for j in range(n):
			if x[i][j] and y[i][j]:
				ans += 1
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = []
	c = 0
	for i in range(n):
		a.append(input())
	b = [[0 for i in range(n)] for i in range(n)]
	prev = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(n):
			if a[i][j] == '#':
				prev[j] += 1
			b[i][j] = prev[j]
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if a[i][j] == '#':
				break
			if b[i][j] == 0:
				c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	(a, v) = ([], [[0 for j in range(n)] for i in range(n)])
	for i in range(n):
		k = list(input())
		a.append(k)
	for i in range(n):
		k = 0
		for j in range(n - 1, -1, -1):
			if a[j][i] == '#':
				k = 1
				break
			elif k == 0:
				v[j][i] = 1
	count = 0
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if a[i][j] == '#':
				break
			elif v[i][j] == 1:
				count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	lr = []
	lc = ['.'] * n
	for i in range(n):
		sr = input()
		sc = ''
		for j in range(n):
			if sr[j] == '#':
				sr = '#' * (j + 1) + sr[j + 1:]
				lc[j] = '#' * (i + 1)
			else:
				lc[j] += '.'
		lr.append(sr)
	ans = 0
	for i in range(n):
		for j in range(n):
			if lr[i][j] == '.' and lc[j][i] == '.':
				ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		s = input()
		l.append(s)
	ans = 0
	f = []
	for i in range(n):
		f.append([0] * n)
	for i in range(n):
		flag = True
		for j in range(n - 1, -1, -1):
			if l[i][j] == '#':
				flag = False
			else:
				if i > 0 and l[i - 1][j] == '.':
					f[i][j] += f[i - 1][j]
				if flag:
					f[i][j] += 1
	print(sum(f[-1]))


t = int(input())
for _ in range(t):
	n = int(input())
	grid = []
	for i in range(n):
		grid.append(list(input()))
	for j in range(n):
		for i in range(n - 1, -1, -1):
			if grid[i][j] == '#':
				break
			grid[i][j] = 1
	ans = 0
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if grid[i][j] == '#':
				break
			if grid[i][j] == 1:
				ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	grid = []
	for _ in range(n):
		grid.append(input())
	res = 0
	vertical = [[0] * n for i in range(n)]
	for c in range(n):
		for i in range(n - 1, -1, -1):
			if grid[i][c] == '#':
				break
			vertical[i][c] = 1
	for r in range(n):
		for i in range(n - 1, -1, -1):
			if grid[r][i] == '#':
				break
			if vertical[r][i]:
				res += 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	grid = []
	dp = [[0] * n for i in range(n)]
	for i in range(n):
		ll = input()
		grid.append(ll)
		if ll[-1] == '.':
			dp[i][-1] = 1
	for i in range(n - 2, -1, -1):
		if grid[0][i] == '#':
			break
		dp[0][i] = dp[0][i + 1]
	for i in range(1, n):
		f = dp[i][-1] == 1
		for j in range(n - 2, -1, -1):
			if grid[i][j] == '#':
				f = False
				continue
			if f:
				dp[i][j] += dp[i - 1][j] + 1
			else:
				dp[i][j] += dp[i - 1][j]
	for i in range(1, n):
		if grid[i][-1] == '#':
			continue
		dp[i][-1] += dp[i - 1][-1]
	print(sum(dp[-1]))


for _ in range(int(input())):
	n = int(input())
	a = [list(input()) for i in range(n)]
	c = 0
	dp = [[0] * n for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if a[i][j] == '#':
				dp[i][j] = 1
	row = [1] * n
	col = [1] * n
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if dp[i][j] == 1:
				row[i] = 0
				col[j] = 0
			if row[i] == 1 and col[j] == 1:
				c += 1
	print(c)


try:
	for _ in range(int(input())):
		n = int(input())
		array = []
		for _ in range(n):
			array.append(list(input()))
		dp = [[1 for jj in range(len(array[0]))] for kk in range(len(array))]
		ans = 0
		blocked = [0] * len(array[0])
		for i in range(len(array) - 1, -1, -1):
			for j in range(len(array[0]) - 1, -1, -1):
				s = 0
				if array[i][j] == '#':
					s = 1
					dp[i][j] = 1
					blocked[j] = 1
					continue
				if j < len(array[0]) - 1:
					bb = dp[i][j + 1]
				else:
					bb = 0
				cache = max(blocked[j], bb, s)
				dp[i][j] = bb
				if cache == 0:
					ans += 1
		print(ans)
except:
	pass


for _ in range(int(input())):
	N = int(input())
	G = []
	for i in range(N):
		G.append(input())
	cnt = 0
	row = [True] * N
	col = [True] * N
	for i in range(N - 1, -1, -1):
		for j in range(N - 1, -1, -1):
			if G[i][j] == '#':
				row[i] = False
				col[j] = False
			if row[i] and col[j]:
				cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(input()))
	dp = [0 for i in range(n)]
	c = 0
	f = 0
	for i in range(n - 1, -1, -1):
		if l[-1][i] == '#':
			dp[i] = 1
			f = 1
		if f == 0:
			c += 1
	for i in range(n - 2, -1, -1):
		f = 0
		for j in range(n - 1, -1, -1):
			if l[i][j] == '#':
				dp[j] = 1
				f = 1
			if dp[j] == 0 and f == 0:
				c += 1
	print(c)


for __ in range(int(input())):
	n = int(input())
	a = []
	b = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		a.append(list(input()))
	for i in range(n):
		if a[n - 1][i] == '.':
			for j in reversed(range(n)):
				if a[j][i] == '#':
					break
				b[j][i] += 1
	for i in range(n):
		if a[i][n - 1] == '.':
			for j in reversed(range(n)):
				if a[i][j] == '#':
					break
				b[i][j] += 1
	ans = 0
	for x in b:
		ans += x.count(2)
	print(ans)


import numpy as np
T = int(input())
for case in range(T):
	N = int(input())
	M = np.zeros((N, N))
	for i in range(N):
		l = str(input())
		for j in range(N):
			if l[j] == '#':
				M[i, j] = 1
	M1 = np.copy(M)
	for i in range(N - 2, -1, -1):
		M1[i, :] = M1[i + 1, :] + M1[i, :]
	M2 = np.copy(M)
	for j in range(N - 2, -1, -1):
		M2[:, j] = M2[:, j + 1] + M2[:, j]
	print(N * N - np.count_nonzero(M1 + M2))


test = int(input())
for _ in range(test):
	n = int(input())
	matrix = []
	for i in range(n):
		temp = list(input())
		matrix.append(temp)
	count = 0
	answer = [[0 for i in range(n)] for j in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if matrix[i][j] == '#':
				break
			answer[i][j] += 1
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if matrix[j][i] == '#':
				break
			answer[j][i] += 1
	for i in range(n):
		for j in range(n):
			if answer[i][j] == 2:
				count += 1
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	grid = []
	for j in range(N):
		grid.append(list(input()))
	for k in range(N):
		for j in range(N - 1, -1, -1):
			if grid[j][k] == '#':
				break
			grid[j][k] = 1
	ans = 0
	for j in range(N):
		for k in range(N - 1, -1, -1):
			if grid[j][k] == '#':
				break
			if grid[j][k] == 1:
				ans += 1
	print(ans)


for t in range(0, int(input())):
	n = int(input())
	arr = []
	for i in range(0, n):
		s = input()
		arr.append(s)
	count = 0
	new_arr = [[0 for i in range(n)] for j in range(n)]
	new_arr2 = [[0 for i in range(n)] for j in range(n)]
	for i in range(0, n):
		if arr[n - 1][i] == '.':
			new_arr[n - 1][i] = 1
		if arr[i][n - 1] == '.':
			new_arr2[i][n - 1] = 1
	for i in range(n - 1, 0, -1):
		for j in range(0, n):
			if new_arr[i][j] == 1 and arr[i - 1][j] == '.':
				new_arr[i - 1][j] = 1
			if new_arr2[j][i] == 1 and arr[j][i - 1] == '.':
				new_arr2[j][i - 1] = 1
	for i in range(0, n):
		for j in range(0, n):
			if new_arr[i][j] == 1 and new_arr2[i][j] == 1:
				count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	mat = []
	cnt = 0
	(row, col) = ([0] * n, [0] * n)
	for z in range(n):
		mat.append(input())
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if mat[i][j] == '#':
				(col[j], row[i]) = (1, 1)
			elif col[j] == 0 and row[i] == 0:
				cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	box = []
	for j in range(n):
		box.append(list(input()))
	for k in range(n):
		for j in range(n - 1, -1, -1):
			if box[j][k] == '#':
				break
			box[j][k] = 1
	ans = 0
	for j in range(n):
		for k in range(n - 1, -1, -1):
			if box[j][k] == '#':
				break
			if box[j][k] == 1:
				ans += 1
	print(ans)


def set_row(G, F, y):
	for i in range(N - 1, -1, -1):
		if G[y][i] != '#':
			F[y][i] += 1
		else:
			break

def set_col(G, F, x):
	for i in range(N - 1, -1, -1):
		if G[i][x] != '#':
			F[i][x] += 1
		else:
			break
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	G = []
	for i in range(N):
		x = list(input())
		G.append(x)
	F = [[0 for i in range(N)] for j in range(N)]
	for i in range(N):
		set_row(G, F, i)
		set_col(G, F, i)
	count = 0
	for i in range(N):
		for j in range(N):
			if F[i][j] == 2:
				count += 1
	ans.append(count)
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	n = int(input())
	m = []
	for i in range(n):
		m.append(input())
	count = 0
	h1 = []
	h2 = []
	for i in range(n):
		j = 0
		while j < n:
			if m[i][n - j - 1] == '#':
				h1.append(n - j - 1)
				break
			j += 1
		else:
			h1.append(n - j - 1)
	for i in range(n):
		j = 0
		while j < n:
			if m[n - j - 1][i] == '#':
				h2.append(n - j - 1)
				break
			j += 1
		else:
			h2.append(n - j - 1)
	c = 0
	x = 0
	for h in h1:
		i = n - 1
		while i > h:
			if h2[i] < x:
				c += 1
			i -= 1
		x += 1
	print(c)


def num_of_mirrors(N, a):
	tot = 0
	dp = [[[0, 0] for i in range(N)] for j in range(N)]
	for i in range(N - 1, -1, -1):
		for j in range(N - 1, -1, -1):
			if a[i][j] == '.':
				if j + 1 == N and i + 1 == N:
					dp[i][j][0] += 1
					dp[i][j][1] += 1
					tot += 1
				elif j + 1 == N or i + 1 == N:
					if j + 1 < N:
						if dp[i][j + 1][0] == 1:
							dp[i][j][0] += 1
							tot += 1
						dp[i][j][1] += 1
					elif i + 1 < N:
						if dp[i + 1][j][1] == 1:
							dp[i][j][1] += 1
							tot += 1
						dp[i][j][0] += 1
				elif dp[i][j + 1][0] == 1 and dp[i + 1][j][1] == 1:
					dp[i][j][0] += 1
					dp[i][j][1] += 1
					tot += 1
				elif dp[i][j + 1][0] == 1:
					dp[i][j][0] += 1
				elif dp[i + 1][j][1] == 1:
					dp[i][j][1] += 1
	return tot
t = int(input())
for i in range(0, t):
	N = int(input())
	l = []
	for j in range(N):
		a = input()
		l.append(a)
	print(num_of_mirrors(N, l))


import sys
import math
from queue import Queue
import heapq

def main(grid):
	dp = [[None for i in range(len(grid[0]))] for j in range(len(grid))]
	south = [[None for i in range(len(grid[0]))] for j in range(len(grid))]
	east = [[None for i in range(len(grid[0]))] for j in range(len(grid))]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			canSee = True if grid[i][j] == '.' else False
			if i + 1 < n:
				canSee = south[i + 1][j] and canSee
			south[i][j] = canSee
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			canSee = True if grid[i][j] == '.' else False
			if j + 1 < n:
				canSee = east[i][j + 1] and canSee
			east[i][j] = canSee
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			canSee = True if grid[i][j] == '.' else False
			if i + 1 < n:
				canSee = south[i + 1][j] and canSee
			if j + 1 < n:
				canSee = east[i][j + 1] and canSee
			dp[i][j] = canSee
	ans = 0
	for i in range(n):
		for j in range(n):
			if dp[i][j]:
				ans += 1
	print(ans)
t = int(input())
for i in range(t):
	n = int(input())
	arr = []
	for j in range(n):
		s = input()
		arr.append([c for c in s])
	main(arr)


n = int(input())
for z in range(0, n):
	k = int(input())
	m = [[]] * k
	for e in range(0, k):
		s = input()
		li = []
		for w in s:
			li.append(w)
		m[e] = li
	dp = [[0] * k for i in range(0, k)]
	c = True
	count = 0
	for i in range(k - 1, -1, -1):
		if m[i][k - 1] == '.':
			if c:
				count = count + 1
			dp[i][k - 1] = True
		else:
			c = False
			dp[i][k - 1] = False
	for e in range(k - 2, -1, -1):
		c = True
		for i in range(k - 1, -1, -1):
			if m[i][e] == '.':
				if c and dp[i][e + 1]:
					count = count + 1
				dp[i][e] = dp[i][e + 1]
			else:
				c = False
				dp[i][e] = False
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	row = [-1] * n
	col = [-1] * n
	matrix = []
	for _ in range(n):
		matrix.append([c for c in input()])
	for i in range(n):
		for j in range(n):
			if matrix[i][j] == '#':
				row[i] = j
				col[j] = i
	count = 0
	for i in range(n):
		for j in range(n):
			if matrix[i][j] == '.':
				if col[j] < i and row[i] < j:
					count += 1
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	grid = []
	for n in range(N):
		grid.append(input())
	v_reachable = [[False for i in range(N)] for j in range(N)]
	for x in range(N):
		for y in range(N - 1, -1, -1):
			if grid[y][x] == '#':
				break
			v_reachable[y][x] = True
	h_reachable = [[False for i in range(N)] for j in range(N)]
	for y in range(N):
		for x in range(N - 1, -1, -1):
			if grid[y][x] == '#':
				break
			h_reachable[y][x] = True
	count = 0
	for y in range(N):
		for x in range(N):
			if v_reachable[y][x] and h_reachable[y][x]:
				count += 1
	print(count)


t = 0
try:
	t = int(input())
except:
	pass

def find_greater_count(x, k):
	sum = 0
	for i in x:
		if k < i:
			sum += 1
	return sum
for _ in range(t):
	n = int(input())
	grid = []
	for __ in range(n):
		grid.append(input())
	mirrors = 0
	right_bounds = []
	bottom_bounds = []
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if grid[i][j] == '#':
				right_bounds.append(n - 1 - j)
				break
		else:
			right_bounds.append(n)
	for j in range(n - 1, -1, -1):
		for i in range(n - 1, -1, -1):
			if grid[i][j] == '#':
				bottom_bounds.append(n - 1 - i)
				break
		else:
			bottom_bounds.append(n)
	for i in range(n):
		mirrors += find_greater_count(right_bounds[:bottom_bounds[i]], i)
	print(mirrors)


for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		u = list(input())
		l.append(u)
	f = []
	for i in range(n):
		f.append([0] * n)
	for i in range(n):
		flag = True
		for j in range(n - 1, -1, -1):
			if l[i][j] == '#':
				flag = False
			else:
				if i > 0 and l[i - 1][j] == '.':
					f[i][j] += f[i - 1][j]
				if flag:
					f[i][j] += 1
	print(sum(f[-1]))


for _ in range(int(input())):
	n = int(input())
	path = []
	rows = [-1] * n
	column = [-1] * n
	count = 0
	for i in range(n):
		a = []
		for j in input():
			a.append(j)
		path.append(a)
	for i in range(n):
		for j in range(n):
			if path[i][j] == '#':
				rows[i] = j
				column[j] = i
	for i in range(n):
		for j in range(n):
			if path[i][j] == '.':
				if rows[i] < j and column[j] < i:
					count += 1
	print(count)


T = int(input())
for k in range(T):
	N = int(input())
	b = [[0] * N + [1] for i in range(N)]
	b.append([1 for i in range(N + 1)])
	d = [[0] * N + [1] for i in range(N)]
	d.append([1 for i in range(N + 1)])
	a = []
	for j in range(N):
		x = input()
		a.append(x)
	c = 0
	for i in range(N - 1, -1, -1):
		for j in range(N - 1, -1, -1):
			if a[i][j] == '.' and b[i][j + 1] == 1:
				b[i][j] = 1
			else:
				b[i][j] = 0
			if a[i][j] == '.' and d[i + 1][j] == 1:
				d[i][j] = 1
			else:
				d[i][j] = 0
			if b[i][j] == 1 and d[i][j] == 1:
				c = c + 1
	print(c)


from collections import defaultdict

def solve(A, n):
	map_row = defaultdict(list)
	map_col = defaultdict(list)
	for row in range(n):
		count = 0
		for col in range(n):
			if A[row][col] == '#':
				count += 1
			map_row[row].append(count)
	for col in range(n):
		count = 0
		for row in range(n):
			if A[row][col] == '#':
				count += 1
			map_col[col].append(count)
	count = 0
	for row in range(n):
		for col in range(n):
			row_count = 1 if A[row][col] == '#' else 0
			row_count = row_count + map_row[row][n - 1] - map_row[row][col]
			col_count = 1 if A[row][col] == '#' else 0
			col_count = col_count + map_col[col][n - 1] - map_col[col][row]
			if row_count + col_count == 0:
				count += 1
	return count
t = int(input())
for k in range(t):
	A = []
	n = int(input())
	for i in range(n):
		s = input()
		A.append(list(s))
	print(solve(A, n))