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: interview

Starter code:

Solutions:
# cook your dish here
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 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 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)