Manhattan distance

Manyland is a grid with N rows and 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 between 1 and N+M−2 inclusive, Danny wants to calculate the number of unordered pairs of distinct houses with distance equal
to d. Please help him!


Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M.
N lines follow. For each i (1≤i≤N), the i-th of these lines contains a binary string with length M; for each j (1≤j≤M), 
the j-th character of this string is '1' if the cell in the i-th row and 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 space-separated integers. For each valid i, the i-th integer
should denote the number of pairs with distance i.


Constraints
1≤T≤3
2≤N,M≤300


Example Input
1
3 4
0011
0000
0100


Example Output
1 0 1 1 0