COETEST5

Nam và Huy đang đánh cờ Caro với nhau, do có việc bận nên hai bạn không thể tiếp tục đánh cờ nhưng họ vẫn muốn tìm ra người chiến thắng. Hai bạn quyết định phân thắng bại bằng việc xem ai có thể chiến thắng với thêm một nước đi. Họ nhờ bạn làm trọng tài để phân xử.

Nhiệm vụ của bạn là: với thêm một nước đi nữa (X hoặc O tùy ý) có thể tìm ra người chiến thắng được hay không?

Trò chơi Caro sẽ kết thúc khi có người chơi đạt được 5 quân cờ giống nhau liên tiếp theo hàng dọc hoặc ngang hoặc chéo.

Trò chơi này tuân thủ quy tắc chặn hai đầu, tức là: Kể cả khi bạn đạt được 5 quân cờ liên tiếp nhưng nếu đối phương chặn ở hai đầu thì bạn vẫn không thể giành chiến thắng.

Lưu ý: Trò chơi chỉ diễn ra trong phạm vi bàn cờ.

Input

Dòng đầu tiên của input là số testcase T (T <= 10).

Dòng tiếp theo gồm 2 số n, m (10 <= n, m <= 15) là kích thước bàn cờ lần lượt là độ dài hàng và cột.

n dòng tiếp theo, mỗi dòng gồm m số tự nhiên trong đó:

0 là ô cờ trống

1 là quân cờ X

2 là quân cờ O

Output

In ra theo định dạng sau: đầu tiên là kí tự "#", tiếp theo là số thứ tự của test case, tiếp theo là khoảng trắng (dấu cách) và cuối cùng là kết quả.

Nếu có người thắng cuộc kết quả in ra 1, không có ai thắng kết quả in ra 0

Example

Input:
3
10 10
0 1 1 2 2 1 0 2 0 0
0 1 1 0 2 1 2 2 1 0
2 2 2 2 0 0 1 0 0 0
1 2 1 2 2 2 2 1 2 0
0 0 1 1 2 1 2 0 1 2
1 2 1 1 0 1 1 2 2 2
2 1 0 1 2 1 0 1 1 1
1 2 0 2 1 1 2 0 0 1
1 2 0 2 2 2 0 1 1 2
1 1 0 0 0 2 2 2 1 1
10 10
1 2 2 2 2 0 1 2 1 0
2 0 1 2 0 2 1 0 0 2
1 2 0 1 2 0 0 0 1 1
1 1 0 1 0 0 2 2 0 1
0 1 2 0 2 1 1 2 0 2
2 0 0 2 1 2 1 0 0 1
1 0 2 1 0 0 1 0 2 1
2 1 1 2 1 2 2 0 1 2
1 0 1 1 1 1 2 2 2 2
0 2 0 2 2 1 2 2 1 2
10 10
1 2 2 1 2 1 1 2 0 0
1 2 1 0 1 0 1 1 2 0
0 0 2 0 1 2 0 2 2 2
2 2 2 1 1 2 0 1 2 2
1 2 2 2 1 1 2 2 0 1
0 1 1 0 1 0 0 2 2 2
0 2 1 0 2 1 1 2 2 2
0 1 1 1 2 0 0 0 0 0
0 2 0 1 0 2 0 0 2 2
0 0 2 0 0 0 0 2 0 0

Output:
#1 1
#2 1
#3 1