COETEST5

Input

Dòng 1 là số lượng test case T (T <= 50)

Dòng tiếp theo là số hàng và cột (bài này luôn là 10 hàng - 10 cột)

10 dòng tiếp theo là input, 0 là vị trí trống, 1 là vị trí có gạch

Các block luôn là 2x1

Output

Đưa ra output trên T dòng tương ứng với T  test case.

Mỗi test case in ra “#tc”, với tc là số thứ tự của test case, đánh số bắt đầu từ 1, tiếp theo là một dấu cách và kết quả tương ứng của test case đó.

Kết quả in ra bao gồm 10 số là độ cao cao nhất ở mỗi cột sau khi tất cả các block rơi xuống.

Example

Input:
5
10 10
1 0 0 0 1 1 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 
0 0 1 1 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 0 0 
0 0 0 1 0 0 1 1 0 0 
0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 1 0 
0 1 0 1 1 0 0 0 0 1 
0 1 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 
10 10
0 0 1 0 0 1 1 0 0 0 
0 0 1 0 0 0 0 0 0 1 
0 0 0 0 1 1 0 0 0 1 
0 1 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 
0 1 1 0 1 1 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 0 0 
0 0 0 1 0 1 1 0 0 0 
10 10
0 0 0 0 0 0 1 0 0 0 
0 1 1 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 1 0 0 0 
1 0 1 1 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 1 0 0 0 
0 0 0 1 1 0 1 0 0 0 
0 0 0 0 0 0 0 0 1 1 
10 10
0 0 0 0 1 1 0 0 0 1 
0 0 0 0 0 0 0 0 0 1 
1 1 0 0 0 0 0 0 0 0 
0 0 0 1 0 1 0 0 0 0 
0 0 0 1 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 0 0 1 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 1 0 1 1 0 0 0 0 
10 10
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
1 1 0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 1 0 0 0 
0 0 1 1 0 0 0 0 1 1

Output:
#1 5 3 4 4 2 2 2 2 1 2
#2 0 3 3 2 3 4 4 0 0 4
#3 2 3 3 2 1 0 6 0 1 1
#4 2 2 1 4 4 4 0 2 0 2
#5 1 1 1 1 0 5 1 0 1 1