After fixing the mercury leak, Kim has arrived in the planning room, where he finds a square map of a field, with $N$ rows and $N$ columns. Each cell in the field is either empty, or has a lookout tower on it. Using his notes, he immediately realises that this field is where the JSA will build their new base!
Kim knows that Soum is a fan of symmetric base design, and will only approve of a base to be built if it is square. Furthermore, Soum also requires that all the rows in the base, and all the columns in the base have exactly one tower square in them. 
This means that a base plan is valid if and only if:
- It is square in shape
- Every row in the base has exactly one lookout tower in it.
- Every column in the base has exactly one lookout tower in it.
Kim notices that all the rows and all the columns in the field have exactly one tower square in them, but he knows that some of them could have been built to throw him off! Can you help Kim find how many valid base plans are possible in this field? Two base plans are considered different if one contains a cell in the grid that the other does not.
Please refer to the samples for more details.

-----Input:-----
- The first line of input contains $T$, the number of testcases.
- The first line of each testcase contains a single integer, $N$, representing the side length of the field.
- The next $N$ lines of each testcase contain a string of length $N$, consisting of only 0 and 1. If position $j$ in string $i$ is 0, it means that this the field has no tower at $[i][j]$, and if it is 1, then this cell does have a tower at $[i][j]$.
It is guaranteed that every row in the input will have exactly one tower, and every column in the input will also have exactly one tower.

-----Output:-----
For each testcase, output a single integer $K$, representing the number of different base plans possible.

-----Subtasks-----
- For all subtasks, $N \leq 2500$ and $T \leq 10$. 
- In addition, the sum of $N$ in any testfile is at most $2500$.
Subtask 1 [28 points] : All the towers will be on the diagonal from the top-left to the bottom-right positions. Formally, all positions where $i = j$ have a tower. And no other position has a tower
Subtask 2 [39 points] : $N \leq 600$
Subtask 3 [33 points] : $N \leq 2500$

-----Sample Input:-----
2
2
10
01
4
1000
0010
0100
0001

-----Sample Output:-----
3
8

-----Explanation:-----

In the first testcase, there are three valid base plans: The entire 2x2 square, the 1x1 square which contains only the cell (1, 1) and the 1x1 square which contains only the cell (2, 2).

In the second testcase, 

There are eight valid base plans:
- The 4x4 square with top left corner at (1, 1)
- The 3x3 square with top left corner at (1, 1)
- The 3x3 square with top left corner at (2, 2)
- The 3x3 square with top left corner at (1, 1)
- The 2x2 square with top left corner at (2, 2)
- The 1x1 square which contains only the cell (1, 1)
- The 1x1 square which contains only the cell (2, 3)
- The 1x1 square which contains only the cell (3, 2)
- The 1x1 square which contains only the cell (4, 4)

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
T = int(input())
ans = []
for _ in range(T):
	z = int(input())
	for k in range(z):
		s = input()
	ans.append(z * (z + 1) // 2)
for ele in ans:
	print(ele)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for j in range(n):
		l.append(list(input()))
	if n == 1:
		print(1)
		continue
	elif n == 2:
		print(3)
		continue
	else:
		val = int(n * (n + 1) / 2)
		count = n - 3 + 1
		flagl = 1
		flagr = 1
		for j in range(n):
			if flagl == 0 and flagr == 0:
				break
			if l[j][j] == '0':
				flagl = 0
			if l[n - j - 1][n - j - 1] == '0':
				flagr = 0
		if flagl == 0 and flagr == 0:
			print(val - count)
		else:
			print(val)


t = int(input())
for i in range(0, t):
	l = []
	N = int(input())
	for j in range(0, N):
		x = input()
		l.append(x)
	print(int(N * (N + 1) / 2))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	ind = []
	for i in range(0, n):
		l1 = input()
		x = list(l1)
		y = x.index('1')
		ind.append(y)
	count = n + 1
	flag = 0
	for i in range(1, n):
		if ind[i] == ind[i - 1] + 1:
			flag = 1
		else:
			flag = 0
			break
	if flag == 1:
		print(int(n * (n + 1) / 2))
		continue
	for i in range(2, n):
		for j in range(0, n):
			if j + i > n:
				break
			s = sum(ind[j:j + i])
			f = min(ind[j:j + i])
			if s - i * f == int((i - 1) * i / 2):
				count += 1
	print(count)


for _ in range(int(input())):
	N = int(input())
	field = []
	for i in range(N):
		field.append(list(map(int, input())))
	print(N * (N + 1) // 2)


for _ in range(int(input())):
	size = int(input())
	power = []
	for i in range(size):
		power.append(input())
	diag = True
	for i in range(size):
		if power[i][i] == '0':
			diag = False
			break
	if diag:
		print(size * (size + 1) // 2)
	else:
		print(size)


import sys
from collections import defaultdict
from itertools import permutations, combinations
import string
from heapq import heapify, heappush, heappop

def solve():
	sys.setrecursionlimit(int(100000.0))
	MOD = int(1000000000.0) + 7
	alphabets = string.ascii_lowercase
	digits = string.digits
	glo = globals
	loc = locals
	get_arr = lambda type_=int: list(map(type_, sys.stdin.readline().rstrip('\n').split()))
	inp = lambda type_=int: type_(sys.stdin.readline().rstrip('\n'))
	pair = lambda type_=int: list(map(type_, sys.stdin.readline().rstrip('\n').split(' ')))
	debug = lambda *args: [(args[i], eval(args[i], args[-1])) for i in range(len(args) - 1)]
	filter_ = lambda fn, arr: list(filter(fn, arr))
	map_ = lambda fn, arr: list(map(fn, arr))
	t = inp()
	for _ in range(t):
		n = inp()
		grid = []
		for i in range(n):
			grid.append(inp(str))
		d = defaultdict(int)
		res = n
		l = []
		for i in range(n):
			s = grid[i]
			for j in range(n):
				if s[j] == '1':
					d[i] = j
					l.append(j)
					break
		for i in range(len(grid)):
			my_set = set()
			my_set2 = set()
			for j in range(i, len(grid)):
				my_set.add(l[j])
				my_set2.add(d[l[j]])
				if my_set == my_set2 and len(my_set) > 1:
					res += 1
		print(res)
solve()


t = int(input())
while t != 0:
	sum1 = 0
	n = int(input())
	for i in range(1, n + 1):
		m = input()
		sum1 += i
	print(sum1)
	t -= 1


try:
	for i in range(int(input())):
		n = int(input())
		c = 0
		for k in range(n):
			s = str(input())
			a = s.find('1')
			if a != k:
				c = c + 1
		a = n * (n + 1) // 2
		print(a - c)
except:
	pass


def fact(n):
	factorial = 1
	if int(n) >= 1:
		for i in range(1, int(n) + 1):
			factorial = factorial * i
	return factorial
t = int(input())
for i in range(t):
	n = int(input())
	s = []
	for j in range(n):
		s.append(input())
	print(int(fact(n) / fact(n - 2) / 2) + n)


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(input())
	x = int(n * (n + 1) / 2)
	print(x)


t = int(input())
while t > 0:
	n = int(input())
	a = []
	for i in range(n):
		temp = input()
		a.append(temp)
	print((n * n + n) // 2)
	t -= 1


def foo(temp, p):
	flag = True
	for d in range(p):
		yet = temp[d]
		if 1 not in yet:
			flag = False
			break
	return flag
T = int(input())
for t in range(T):
	N = int(input())
	lst = []
	count = 0
	temp = []
	for n in range(N):
		num = list(map(int, str(input())))
		x = num.index(1)
		y = (n, x)
		temp.append(y)
		lst.append(num)
	print(int(N * (N + 1) / 2))


t = int(input())
for _ in range(t):
	m = []
	n = int(input())
	for i in range(n):
		s = input()
		l = list(s)
		m.append(l)
	(q, ans) = ([], [])
	for i in range(len(m)):
		for j in range(len(m)):
			if m[i][j] == '1':
				ans.append((i + 1, j + 1))
				q.append([i + 1, j + 1])
	for i in range(len(q)):
		for j in range(i + 1, len(q)):
			(x, y) = ([0, 0], [0, 0])
			r = abs(q[i][0] - q[j][0])
			c = abs(q[i][1] - q[j][1])
			shift = abs(r - c)
			if shift == 0:
				x = min(q[i][0], q[i][1])
				y = max(q[j][0], q[j][1])
				p = ((x, x), (y, y))
			else:
				if r > c:
					(a1, a2) = (min(q[i][1], q[j][1]), max(q[i][1], q[j][1]))
					if a2 + shift <= n:
						x[1] = a1
						y[1] = a2 + shift
						x[0] = min(q[i][0], q[j][0])
						y[0] = max(q[i][0], q[j][0])
					elif a1 - shift >= 1:
						x[1] = a1 - shift
						y[1] = a2
						x[0] = min(q[i][0], q[j][0])
						y[0] = max(q[i][0], q[j][0])
				elif q[i][0] - shift >= 1:
					x[0] = q[i][0] - shift
					x[1] = min(q[i][1], q[j][1])
					y[0] = q[j][0]
					y[1] = max(q[i][1], q[j][1])
				elif q[j][0] + shift <= n:
					x[0] = q[i][0]
					x[1] = min(q[i][1], q[j][1])
					y[1] = max(q[i][1], q[j][1])
					y[0] = q[j][0] + shift
				p = ((x[0], x[1]), (y[0], y[1]))
			ans.append(p)
	d = {}
	for i in ans:
		d[i] = 1
	print(len(d))


from collections import Counter
for t in range(int(input())):
	n = int(input())
	pos = [(i, input().strip().find('1')) for i in range(n)]
	c = n
	for i in range(2, n + 1):
		multiset = Counter()
		for k in range(i):
			multiset[pos[k][0]] += 1
			multiset[pos[k][1]] += 1
		if len(multiset) == i:
			c += 1
		for j in range(1, n - i + 1):
			multiset[pos[j - 1][0]] -= 1
			if multiset[pos[j - 1][0]] == 0:
				del multiset[pos[j - 1][0]]
			multiset[pos[j - 1][1]] -= 1
			if multiset[pos[j - 1][1]] == 0:
				del multiset[pos[j - 1][1]]
			multiset[pos[j + i - 1][0]] += 1
			multiset[pos[j + i - 1][1]] += 1
			if len(multiset) == i:
				c += 1
	print(c)


for _ in range(int(input())):
	a = []
	n = int(input())
	for i in range(n):
		s = input()
		a.append(s)
	print(n * (n + 1) // 2)


for __ in range(int(input())):
	n = int(input())
	for i in range(n):
		s = input()
	c = int(n * (n + 1) / 2)
	print(c)


from sys import stdin as s
t = int(s.readline())
while t:
	t -= 1
	n = int(s.readline())
	for _ in range(n):
		a = s.readline()
	print(n * (n + 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	swa = 0
	suma = 0
	for j in range(0, n):
		s = input()
		for k in range(0, n):
			if s[k] == '1':
				swa = swa + abs(k - j)
	while n >= 1:
		suma += n
		n = n - 1
	if swa == 0:
		print(suma)
	else:
		print(suma - swa + 1)


T = int(input())
for i in range(0, T):
	lst2 = []
	N = int(input())
	for j in range(0, N):
		lst = input()
		lst2.append(lst)
	print(int(N * (N + 1) / 2))


for _ in range(int(input())):
	n = int(input())
	for q in range(n):
		data = input()
	count = 0
	ans = n * (n + 1) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	power = []
	for i in range(n):
		power.append(input())
	d = True
	for i in range(n):
		if power[i][i] != '1':
			d = False
			break
	if d:
		ans = n * (n + 1) // 2
		print(ans)
	else:
		print(0)