Chefland is a grid with N$N$ rows and M$M$ columns. Each cell of this grid is either empty or contains a house. The distance between a pair of houses is the Manhattan distance between the cells containing them.
For each d$d$ between 1$1$ and N+M−2$N+M-2$ inclusive, Chef wants to calculate the number of unordered pairs of distinct houses with distance equal to d$d$. Please help him!

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains two space-separated integers N$N$ and M$M$.
- N$N$ lines follow. For each i$i$ (1≤i≤N$1 \le i \le N$), the i$i$-th of these lines contains a binary string with length M$M$; for each j$j$ (1≤j≤M$1 \le j \le M$), the j$j$-th character of this string is '1' if the cell in the i$i$-th row and j$j$-th column contains a house or '0' if it is empty.

-----Output-----
For each test case, print a single line containing N+M−2$N+M-2$ space-separated integers. For each valid i$i$, the i$i$-th integer should denote the number of pairs with distance i$i$.

-----Constraints-----
- 1≤T≤3$1 \le T \le 3$
- 2≤N,M≤300$2 \le N, M \le 300$

-----Subtasks-----
Subtask #1 (50 points): N,M≤50$N, M \le 50$
Subtask #2 (50 points): original constraints

-----Example Input-----
1
3 4
0011
0000
0100

-----Example Output-----
1 0 1 1 0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for a in range(int(input())):
	(N, M) = map(int, input().split())
	b = []
	for o in range(N):
		b.append(input())
	c = []
	for d in b:
		f = []
		for e in range(len(d)):
			if d[e] == '1':
				f.append(e)
		c.append(f)
	i = []
	for g in range(len(c)):
		for h in range(len(c[g])):
			for j in range(len(c)):
				for k in range(len(c[j])):
					if j > g or (j == g and k > h):
						if c[g][h] - c[j][k] >= 0:
							i.append(c[g][h] - c[j][k] + j - g)
						else:
							i.append(-1 * (c[g][h] - c[j][k]) + j - g)
	l = [m for m in range(1, N + M - 1)]
	for n in l:
		print(i.count(n), end=' ')


for _ in range(int(input())):
	mat = []
	(n, m) = map(int, input().split())
	for i in range(n):
		mat.append(list(input()))
	d = [0] * (n + m)
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '1':
				for x in range(n):
					for y in range(m):
						if mat[x][y] == '1':
							d[abs(x - i) + abs(y - j)] += 1
	for i in range(1, n + m - 1):
		print(d[i] // 2, end=' ')


from math import *
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
	l = []
	for i in range(n):
		for j in range(m):
			if a[i][j] == '1':
				l.append((i, j))
	d = {}
	for i in range(1, n + m - 2 + 1):
		d[i] = 0
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			dis = abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1])
			d[dis] += 1
	for i in range(1, n + m - 2 + 1):
		print(d[i], end=' ')


from itertools import combinations
from scipy.spatial.distance import pdist
import numpy as np

def solve():
	houses = []
	(n, m) = list(map(int, input().split()))
	for i in range(n):
		s = input()
		tmp = [i for (i, x) in enumerate(s) if x == '1']
		houses = houses + [[i, j] for j in tmp]
	counter = [0] * (n + m - 1)
	dis = pdist(np.array(houses), 'cityblock').astype(int)
	for i in dis:
		counter[i] += 1
	return [counter[i] for i in range(1, n + m - 1)]
for _ in range(int(input())):
	print(*solve())


from collections import defaultdict
from itertools import combinations
from scipy.spatial.distance import pdist

def solve():
	houses = []
	(n, m) = list(map(int, input().split()))
	for i in range(n):
		s = input()
		tmp = [i for (i, x) in enumerate(s) if x == '1']
		houses = houses + [(i, j) for j in tmp]
	counter = defaultdict(int)
	dis = pdist(houses, 'cityblock')
	for i in dis:
		counter[i] += 1
	return [counter[i] for i in range(1, n + m - 1)]
for _ in range(int(input())):
	print(*solve())


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	li = []
	for i in range(n):
		for j in range(m):
			if l[i][j] == '1':
				li.append((i + 1, j + 1))
	di = [0 for i in range(n + m - 2)]
	for x in range(len(li)):
		for y in li[x + 1:]:
			z = li[x]
			distance = abs(z[0] - y[0]) + abs(z[1] - y[1])
			di[distance - 1] = di[distance - 1] + 1
	for x in di:
		print(x, end=' ')
	print()


from collections import defaultdict
from itertools import combinations

def norm(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve():
	houses = []
	(n, m) = list(map(int, input().split()))
	for i in range(n):
		s = input()
		tmp = [i for (i, x) in enumerate(s) if x == '1']
		houses = houses + [(i, j) for j in tmp]
	counter = defaultdict(int)
	for (a, b) in combinations(houses, 2):
		counter[norm(a, b)] += 1
	return [counter[i] for i in range(1, n + m - 1)]
for _ in range(int(input())):
	print(*solve())


class Point(object):

	def __init__(self, x, y):
		(self.x, self.y) = (x, y)

	def distance(self, other):
		return abs(self.x - other.x) + abs(self.y - other.y)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(l, dist) = ([], [0] * (n + m - 1))
	for i in range(n):
		c = input()
		for j in range(m):
			if c[j] == '1':
				l.append(Point(i, j))
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			dist[l[i].distance(l[j])] += 1
	dist.pop(0)
	for i in dist:
		print(i, end=' ')
	print()


from itertools import combinations

class Point(object):

	def __init__(self, x, y):
		(self.x, self.y) = (x, y)

	def distance(self, other):
		return abs(self.x - other.x) + abs(self.y - other.y)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(l, dist) = ([], [0] * (n + m - 1))
	for i in range(n):
		c = input()
		for j in range(m):
			if c[j] == '1':
				l.append(Point(i, j))
	total = 0
	for i in combinations(l, 2):
		dist[i[0].distance(i[1])] += 1
	dist.pop(0)
	for i in dist:
		print(i, end=' ')
	print()


T = int(input())
for i in range(T):
	l = list(map(int, input().split()))
	(n, m) = (l[0], l[1])
	z = []
	distance = [0] * (m + n - 1)
	for i in range(n):
		arr = list(map(int, input()))
		for (j, v) in enumerate(arr):
			if v:
				z.append((i, j))
				for pt in z:
					d = abs(pt[0] - i) + abs(pt[1] - j)
					distance[d] += 1
	print(*distance[1:])


T = int(input())

def dist(z, i, j):
	return abs(z[i][0] - z[j][0]) + abs(z[i][1] - z[j][1])
for i in range(T):
	l = list(map(int, input().split()))
	(n, m) = (l[0], l[1])
	grd = [list(map(int, input())) for i in range(n)]
	z = []
	for (i, r) in enumerate(grd):
		for (j, v) in enumerate(r):
			if v:
				z.append((i, j))
		distance = [0] * (n + m - 2)
		for i in range(len(z)):
			for j in range(i + 1, len(z)):
				d = dist(z, i, j)
				distance[d - 1] += 1
	print(*distance)