Để chuẩn bị làm một cây đàn T'rưng cần tìm được cây tre hoặc vầu cái, có đốt dài và đều, dáng thuôn, không có lỗi như nứt, lỗ sâu, . . . Tóm lại, tìm được một cây ưng ý là rất khó. Một nghệ nhân, khi vào rừng hái lá thuốc tìm một cây tre rất ưng ý, nhưng đường đi ra phải qua một hẻm núi độ rộng ~n~ và dài ~m~ bước chân.

Có thể coi hẻm núi như lưới ô vuông ~n×m~, một số ô có đá cao. Cây tre vác trên vai nên khi đi nó sẽ song song với một cạnh của hẻm núi. Cần phải đi từ trái sang phải. Có thể vào hẻm từ ô bất kỳ bên trái với cây tre song song cạnh trái. Khi cây tre đang ở hướng dọc, chỉ có thể di chuyển dọc lên trên hoặc xuống dưới, nếu cây tre đang ở hướng ngang – chỉ có thể di chuyển sang trái hoặc phải. Trong trường hợp cần chuyển hướng có thể chống một đầu cây tre xuống đất, dựng thẳng đứng và cho đổ sang hướng song song với cạnh kia. Dĩ nhiên tre phải được nằm trên các ô không có đá cao. Để ra khỏi hẻm núi phải tới được ô ở cạnh phải với cây tre nằm song song cạnh này. Cần chặt cây tre thành các đoạn ngắn để mang về. Các đoạn đó phải càng dài càng tốt để có nhiều lựa chọn cắt khúc khi làm đàn.

Trạng thái hẻm núi được thể hiện bằng bảng ký tự kích thước ~n×m~, ký tự '.' chỉ vị trí trống, '#' chỉ ô có đá.

Hãy xác định độ dài lớn nhất của đoạn tre có thể mang qua (đơn vị độ dài là cạnh của ô).

Dữ liệu

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~ (~1 ≤ n, m ≤ 300~),
• Mỗi dòng trong ~n~ dòng sau chứa xâu ~s~ độ dài ~m~ mô tả trạng thái một dòng của hẻm núi.

Kết quả

• Đưa ra một số nguyên – độ dài lớn nhất của đoạn tre có thể mang qua.

Sample input

3 5
...##
.#.#.
##...

Sample output

2

Nguồn: Thầy Tùng