COETEST5

Trong giới luật chơi cờ, có một kiểu chơi là phá thế cờ. Kiểu chơi này không giải quyết thắng thua bằng cách tìm ra người chiến thắng mà người ra đề sẽ sắp xếp trước toàn bộ bàn cờ, bạn sẽ được đi một nước cờ quyết định, nếu nước cờ đó thỏa mãn yêu cầu của người ra đề thì bạn đã phá được thế cờ. Có rất nhiều cách chơi, tuy nhiên trò chơi bạn sẽ tham gia có tên là cờ lật, cách chơi cơ bản như sau:

   Trên bàn cờ sẽ có các quân cờ trắng, quân cờ đen và các ô chưa đi. Bàn cờ đã được người ra đề sắp xếp trước. Bạn được phép đặt thêm một quân cờ (trắng hoặc đen do bạn chọn) sao cho số lượng quân cờ bạn chọn là lớn nhất, khi đó bạn là người chiến thắng. Trò chơi này có một luật như sau:

Ví dụ: 1 là cờ đen, 0 là cờ trắng.

Nếu ta đặt cờ đen vào vị trí X, bàn cờ sẽ trở thành:

Số ô đen nhiều nhất là :  8.

Nếu đặt cờ đen vào vị trí y thì chỉ ăn đc thêm 1 ô

X chính là vị trí phá thế cờ.

Input

Dòng đầu tiên là số lượng testcase T.

Dòng tiếp theo là 2 số n, m lần lượt là số hàng và số cột của bàn cờ.

Trong n dòng tiếp theo, mỗi dòng thứ i gồm m số trong đó:

• -1 là ô cờ trống.
• 0 là quân cờ trắng.
• 1 là quân cờ đen.

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 là số quân cờ lớn nhất bạn có thể đạt được khi phá thế cờ.

Example

Input:
3
10 10
-1 -1 0 1 -1 -1 0 0 1 0 
0 0 0 -1 -1 1 0 1 0 -1 
0 1 0 1 1 1 -1 0 -1 -1 
0 1 -1 1 1 -1 0 1 0 -1 
1 1 -1 1 -1 1 1 -1 0 0 
0 0 -1 1 0 -1 1 -1 1 1 
0 0 -1 0 1 -1 0 0 0 0 
-1 -1 0 0 0 0 1 1 0 0 
-1 0 1 -1 1 1 -1 -1 0 -1 
1 -1 0 -1 -1 0 -1 -1 -1 -1 

10 10
0 0 1 1 -1 0 -1 -1 -1 1 
-1 1 1 1 1 1 0 -1 0 0 
1 1 0 -1 -1 1 1 1 -1 0 
1 -1 1 -1 -1 0 1 0 1 1 
-1 -1 0 -1 -1 0 -1 0 -1 -1 
1 0 0 1 0 0 0 0 -1 1 
1 -1 1 0 -1 1 1 -1 0 1 
1 1 0 0 0 0 -1 1 -1 1 
0 -1 1 0 1 -1 -1 1 0 0 
1 -1 -1 0 -1 1 -1 -1 1 0 

10 10
-1 0 -1 -1 0 0 0 -1 -1 -1 
1 0 -1 0 0 1 0 0 1 0 
1 0 1 0 0 -1 1 0 -1 1 
0 1 -1 1 0 0 1 1 0 1 
1 1 1 0 1 0 1 -1 0 0 
0 -1 0 0 0 -1 0 -1 0 1 
0 -1 0 -1 -1 1 0 0 0 1 
1 -1 0 -1 1 -1 1 -1 0 0 
-1 0 0 1 -1 -1 1 1 -1 0 
-1 0 1 0 -1 0 -1 1 -1 -1

Output:
#1 44
#2 42
#3 47