Райан і Ларрі вирішили, що їх горіхи не дуже приємні на смак. Проте є декілька горіхів, розташованих в деяких місцях острова, і вони дуже смачні! Але оскільки хлопці ліниві та жадібні, то вони хочуть знати найкоротший шлях, по якому можна зібрати всі горіхи. Чи можете Ви їм допомогти? \InputFile Перший рядок кожного тесту містить розміри прямокутного острова \textbf{x} та\textit{ }\textbf{y} (\textbf{x}, \textbf{y} ≤ \textbf{20}). Далі слідують \textbf{x} рядків по \textbf{y} символів, що описують карту місцевості. Вона складається з символів '\textbf{.}', '\textbf{#}' та '\textbf{L}'. Спочатку Ларрі і Райан знаходяться в '\textbf{L'}, горіхи позначаються символами '\textbf{#}'. Хлопці за один крок можуть потрапити в будь-яку з восьми сусідніх клітин. Кількість клітин, у яких можуть розташовуватися горіхи, не більша за \textbf{15}. Клітинка з символом '\textbf{L}' на карті усього одна. \OutputFile Для кожної карти в окремому рядку виведіть найменшу кількість кроків, за яку можна стартувавши з клітинки '\textbf{L}', зібрати усі горіхи і повернутися в '\textbf{L}'.