Hai con thiên nga đang ở trong một cái hồ lớn, nhưng chúng lại đang bị chia cắt bởi băng đóng trong hồ nước. Hồ nước có dạng hình chữ nhật được chia thành ~R~ dòng ~C~ cột. Một số ô trong hồ bị băng đóng. Mùa xuân tới dần, băng trong hồ tan dần -- mỗi ngày băng ở tất cả những ô tiếp xúc với nước đang ấm dần trong hồ (tức là kề cạnh một ô không bị đóng băng) sẽ tan ra.

Thiên nga có thể di chuyển tự do ở những ô chứa nước nhưng không thể đi qua những ô bị đóng băng. Bạn hãy tính xem sau bao nhiêu ngày thì đôi thiên nga của chúng ta có thể gặp nhau

Input

• Dòng đầu tiên chứa ~2~ số ~R~ và ~C~, ~1 \leq R~, ~C \leq 1500~.
• Mỗi dòng trong ~R~ dòng tiếp theo chứa ~C~ kí tự mô tả hồ nước tại thời điểm hiện tại: '. ' (dot) thể hiện ~1~ ô chứa nước, 'X' thể hiện ~1~ ô bị đóng băng, và 'L' thể hiện ô có thiên nga. Có chính xác ~2~ ô chữ ~L~.

Output

• Một dòng duy nhất chứa số ngày đôi thiên nga có thể gặp nhau.

Sample Input

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

Sample Output

3