Є лабіринт розміром \(H*W\) (\(H\) рядків, \(W\) стовпчиків). Робот може рухатись з клітинки, в будь-яку з чотирьох сусідніх (крім клітинок стін), і не виходити за межі лабіринту.
Робот завжди рухається найкоротшим можливим шляхом.
Оберіть стартову і фінішну точку в лабіринті таким чином, щоб відстань пройдена роботом була якомога більша.

Формат вхідних даних

В першому рядку цілі числа \(H,W\) (\(1 \le H,W \le 20\))
В наступних \(H\) рядках міститься по \(W\) символів. Символ # позначає стіну, символ . - вільну клітинку.

Формат вихідних даних

Виведіть єдине число - найдовший можливий шлях робота від старту до фінішу (якщо робот завжди рухається найкоротшим шляхом)

Приклад вхідних даних-1

3 3
...
...
...

Приклад вихідних даних-1

4

Приклад вхідних даних-2

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

Приклад вихідних даних-2

10