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 ≤ 2500$ and $T ≤ 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 ≤ 600$

Subtask 3 [33 points] : $N ≤ 2500$

----- Sample Input 1 ------ 
	2
	2
	10
	01
	4
	1000
	0010
	0100
	0001
----- Sample Output 1 ------ 
	3
	8
----- explanation 1 ------ 
![fig1]

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

![fig1]

In the second testcase, 

![fig1]

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)

![fig1]

Difficulty: HARD
Tags: Data structures

Amortized analysis

Range queries

Segment trees revisited
Skill types: Amortized analysis

Data structures

Range queries

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		m = int(input())
		print(1)
	else:
		m = []
		s = []
		for j in range(n):
			l = input()
			x = l.index('1')
			s.append(x)
			m.append(l)
		c = 0
		for k in range(n):
			l1 = s[k]
			l2 = s[k]
			for z in range(k, n):
				l1 = min(s[z], l1)
				l2 = max(s[z], l2)
				if l2 - l1 == z - k:
					c += 1
		print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		m = int(input())
		print(1)
	else:
		m = []
		indexes = []
		for i in range(n):
			l = input()
			temp = l.index('1')
			indexes.append(temp)
			m.append(l)
		counter = 0
		for i in range(n):
			left = indexes[i]
			right = indexes[i]
			for j in range(i, n):
				left = min(indexes[j], left)
				right = max(indexes[j], right)
				if right - left == j - i:
					counter += 1
		print(counter)


for i1 in range(int(input())):
	n = int(input())
	l = []
	c = n
	for j in range(n):
		s = input()
		l += [s.find('1')]
	for i in range(n):
		mi = l[i]
		su = l[i]
		for j in range(i + 1, n):
			if l[j] < mi:
				mi = l[j]
			su += l[j]
			y = j - i + 1
			if y * mi + y * (y - 1) // 2 == su:
				c += 1
	print(c)


def findt(l):
	if len(l) == 1:
		return
	for i in range(2, len(l) + 1):
		v = l[:i]
		if max(v) - min(v) == i - 1:
			c += 1
	findt(l[1:])
for i1 in range(int(input())):
	n = int(input())
	l = []
	c = n
	for j in range(n):
		s = input()
		l += [s.find('1')]
	for i in range(n):
		mi = l[i]
		ma = l[i]
		for j in range(i + 1, n):
			if l[j] > ma:
				ma = l[j]
			if l[j] < mi:
				mi = l[j]
			if ma - mi == j - i:
				c += 1
	print(c)


T = int(input())
for i in range(T):
	N = int(input())
	lis = []
	for j in range(N):
		inp = input()
		for k in range(N):
			if inp[k] == '1':
				lis.append(k)
				break
	sol = 0
	for j in range(N):
		count = lis[j]
		mini = count
		for k in range(j + 1, N):
			count += lis[k]
			if lis[k] < mini:
				mini = lis[k]
			if count == (k - j + 1) * (2 * mini + (k - j)) / 2:
				sol += 1
	print(sol + N)


t = int(input())
while t > 0:
	n = int(input())
	l = []
	l.append(0)
	for i in range(1, n + 1):
		c = input()
		for j in range(n):
			if c[j] == '1':
				l.append(j + 1)
	sum1 = 0
	for j in range(1, n + 1):
		min1 = l[j]
		max1 = l[j]
		for k in range(j, n + 1):
			min1 = min(min1, l[k])
			max1 = max(max1, l[k])
			if max1 - min1 == k - j:
				sum1 += 1
	print(sum1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		s = input()
		ind = s.index('1') + 1
		a.append(ind)
	ans = n
	for i in range(n):
		mini = a[i]
		maxi = a[i]
		arr = []
		for x in range(i + 1, n):
			mini = min(mini, a[x])
			maxi = max(maxi, a[x])
			if maxi - mini == x - i:
				ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		row = input()
		arr.append(row.index('1'))
	res = 0
	for i in range(n):
		mi = arr[i]
		ma = arr[i]
		for j in range(i, n):
			ma = max(ma, arr[j])
			mi = min(mi, arr[j])
			if ma - mi == j - i:
				res += 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	s = []
	for _ in range(n):
		l = input()
		s.append(l.index('1') + 1)
	ans = 0
	for i in range(n):
		mx = -1
		mn = 10 ** 9
		for j in range(i, n):
			mx = max(mx, s[j])
			mn = min(mn, s[j])
			if mx - mn + 1 == j - i + 1:
				ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	v = []
	for i in range(n):
		v.append((i, input().index('1')))
	answer = 0
	for i in range(len(v)):
		r_left = 0
		r_right = 0
		c_left = 0
		c_right = 0
		for j in range(i, len(v)):
			if v[j][0] - v[i][0] < r_left:
				r_left = v[j][0] - v[i][0]
			if v[j][0] - v[i][0] > r_right:
				r_right = v[j][0] - v[i][0]
			if v[j][1] - v[i][1] < c_left:
				c_left = v[j][1] - v[i][1]
			if v[j][1] - v[i][1] > c_right:
				c_right = v[j][1] - v[i][1]
			if abs(r_right - r_left) <= j - i and abs(c_right - c_left) <= j - i:
				answer += 1
	print(answer)


for __ in range(int(input())):
	n = int(input())
	a = []
	loc = [0] * 2505
	ans = 0
	for i in range(n):
		a.append(input())
	for i in range(n):
		for j in range(n):
			if a[i][j] == '1':
				loc[i] = j
	for i in range(n):
		(mn, mx) = (loc[i], loc[i])
		for j in range(i, n):
			mn = min(mn, loc[j])
			mx = max(mx, loc[j])
			if mx - mn == j - i:
				ans += 1
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	arr = []
	for i in range(n):
		s = input()
		arr.append(s.find('1'))
	ans = 0
	for i in range(len(arr)):
		l = r = arr[i]
		for j in range(i, len(arr)):
			l = min(arr[j], l)
			r = max(arr[j], r)
			if r - l == j - i:
				ans += 1
	print(ans)
	t -= 1


from math import factorial
for t in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		temp = input()
		l.append(temp.index('1'))
	res = 0
	for i in range(n):
		mmin = l[i]
		mmax = l[i]
		for j in range(i, n):
			mmin = min(mmin, l[j])
			mmax = max(mmax, l[j])
			if mmax - mmin == j - i:
				res += 1
	print(res)


for _ in range(int(input())):
	N = int(input())
	array = []
	ans = 0
	for i in range(N):
		a = input()
		array.append(a.index('1'))
	for i in range(N):
		array_subset = [array[i]]
		mx = array_subset[0]
		mn = array_subset[0]
		ans += 1
		for j in range(i + 1, N):
			k = array[j]
			array_subset.append(k)
			mn = min(mn, k)
			mx = max(mx, k)
			if mx - mn == j - i:
				ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	b = [0 for i in range(n)]
	for i in range(n):
		a = input()
		b[i] = a.index('1')
	s = 0
	for i in range(n):
		s += 1
		mi = b[i]
		ma = b[i]
		for j in range(i - 1, -1, -1):
			ma = max(ma, b[j])
			mi = min(mi, b[j])
			if ma - mi == i - j:
				s += 1
	print(s)


T = int(input())
for _ in range(T):
	n = int(input())
	A = []
	for i in range(n):
		s = input()
		A.append(s.index('1'))
	c = 0
	for i in range(n):
		s = 0
		v = A[i]
		for j in range(i, n):
			if A[j] < v:
				v = A[j]
			s = s + A[j] + 1
			p = j - i + 1
			s1 = s - (j - i + 1) * v
			if s1 == p * (p + 1) // 2:
				c = c + 1
	print(c)