Frogger
Філіп Дж. Жаба просто хотів поплавати посеред дня, але, як це часто буває у жаб, опинився посеред жвавої вулиці. Допоможіть Філу зрозуміти, скільки часу він буде стрибати по гарячому асфальту, перш ніж знайде шлях до прохолодної води.
Філ може стрибати на одну клітинку горизонтально або вертикально за секунду. Він може стрибати лише на дорогу, траву або воду. Крім того, він не може займати клітинку, зайняту автомобілем. Філ і автомобілі рухаються одночасно, тобто Філ може "перестрибнути" через автомобіль, що наближається. Філ також може залишатися на тій самій клітинці, якщо захоче. Усі горизонтальні рухи циклічні (наприклад, стрибок вправо з крайнього правого стовпця переміщує Філа в крайню ліву колонку). Автомобілі рухаються горизонтально в напрямку, вказаному на карті ('<' означає вліво, '>' означає вправо) зі швидкістю одна клітинка за секунду і ніколи не стикаються з чимось.
Вхідні дані
Вхід починається з одного цілого числа, що вказує кількість тестових карт. Кожна карта починається з двох цілих чисел R і C (0 < R, C ≤ 30), що вказують кількість рядків і стовпців відповідно, за якими слідують R рядків, кожен C символів завдовжки, що визначають карту. Можливі символи карти:
Філ ('') - Початкове місце розташування Філа. Кожна карта містить рівно одне. Завжди вказує на дорогу під ним.
Дерево ('T') - Непрохідне.
Трава ('.') - Філ може вільно рухатися по траві.
Дорога ('-') - Гаряче!
Автомобіль ('<', '>') - Завжди вказує на дорогу під ним.
Вода (' ') - Мета Філа.
Вихідні дані
Для кожної карти виведіть рядок, що містить найменшу кількість секунд, які Філ повинен провести на дорозі, щоб дістатися до води, або рядок "Непрохідно", якщо шлях до води не існує.