Знаменитый искатель приключений Индиана Джонс попал в ловушку! Он оказался заперт в прямоугольной комнате размером N × M, пол которой разделён на квадратные клетки 1 × 1. По вертикали клетки комнаты нумеруются от 1 до N сверху вниз, по горизонтали — от 1 до M слева направо.

На каждой из клеток пола нарисована цифра от 1 до 9. Индиана Джонс моментально сообразил, что эти цифры означают не что иное, как период срабатывания встроенных в пол горелок: каждую секунду, номер которой делится на изображённое на клетке число, из отверстий в полу бьют мощные языки пламени, причиняющие одну единицу урона, если на них наступить.

Изначально (в первую секунду) Индиана Джонс стоит в клетке (1; 1). В каждую следующую секунду он может либо остаться стоять в текущей клетке, либо перешагнуть в любую из клеток, имеющих общую сторону с текущей. В клетке (N; M) проделан люк, ведущий на свободу.

Цель Индианы Джонса — добраться до выхода, получив по пути минимальное количество урона. Но ему надо действовать быстро, так как по прошествии T секунд вся комната самоуничтожится.

Подскажите ему, как выбраться из ловушки с наименьшими потерями.