Степан має лабіринт, який являє собою сітку клітин \(H \times W\) з \(H\) горизонтальними рядками та \(W\) вертикальними стовпцями. Клітинка у \(i\)-му рядку та \(j\)-му стовпці є «стіна», якщо \(S_{ij}\) дорівнює \(\text{#}\), і «дорога», якщо \(S_{ij}\) дорівнює \('.'\). З дороги ви можете перейти до горизонтальної або вертикальної суміжної клітини з дорогою. Ви не можете вийти з лабіринту, перейти до клітини стіни або рухатися по діагоналі. Степан вибере початкову та кінцеву клітинку, яка може бути будь-якою клітинкою з дорогою, і запропонує лабіринт Андрію. Потім Андрій переміститься від початкової клітини до кінцевої за мінімальну кількість необхідних ходів.

Знайдіть максимально можливу кількість ходів, які може зробити Андрій для запропонованого лабіринту.

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

Перший рядок містить цілі числа \(H, W\) (\(1 \le H,W \le 20\)), які розділюються пропуском.

Наступні  \(H\) рядків містять по \(W\) символів \(S_{ij}\) (\(S_{ij} = '\#' , '.'\))

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

У вихідний потік виведіть шукану кількість ходів.

Примітка

До прикладу 1:

Якщо Степан вибирає верхню ліву клітинку як початкову, а нижню праву — як кінцеву, то Андрій має зробити чотири ходи.

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

3 3
...
...
...

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

4

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

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

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

10