giaminh2211 vừa có bài test CP. Nội dung bài toán như sau:

Cho một bảng ~n*m~, ô (~i, j~) chứa một trong ba số nguyên (~0, 1, 2~):

• 0: không tồn tại gì ở ô (~i, j~)
• 1: tồn tại một máy phát ở ô (~i, j~)
• 2: tồn tại một thiết bị điện tử ở ô (~i~, ~j~)

Độ mạnh của máy phát là ~d~. Máy phát tại ô (~i~, ~j~) sẽ phát sóng cho các thiết bị tại vị trí (~x~, ~y~) thỏa mãn khoảng cách Manhattan giữa (~i~, ~j~) và (~x~, ~y~) bé hơn hoặc bằng ~d~.

Hãy tìm ~d~ nhỏ nhất để tất cả thiết bị được phát sóng.

giaminh2211 đã giải được bài toán trên, bạn có thể làm được như vậy không?

Nhắc lại: Khoảng cách Manhattan giữa hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ được tính bằng công thức: ~{Manhattan Distance} = |x_2 - x_1| + |y_2 - y_1|~

INPUT

• Dòng đầu tiên chứa số nguyên dương ~t~ là số test case (~t \le 5~)
• Dòng đầu tiên của mỗi test chứa hai số nguyên ~n~ và ~m~ là kích thước bảng.
• ~n~ dòng tiếp theo của mỗi test, mỗi dòng chứa ~m~ số nguyên mô tả bảng.

OUTPUT

• Với mỗi test case in ra trên một dòng số nguyên ~d~, là độ mạnh nhỏ nhất của máy phát sao cho tất cả thiết bị đều được phát sóng.

SAMPLE INPUT

1
3 3
1 0 1
0 2 0
1 0 1

SAMPLE OUTPUT

2

SUBTASKS