Іграшковий лабіринт є прозорою плоскою прямокутною коробкою, всередині якої є перешкоди і переміщається кулька. Лабіринт можна нахиляти ліворуч, праворуч, до себе або від себе, після кожного нахилу кулька переміщається в заданому напрямку до найближчої перешкоди або до стінки лабіринту, після чого зупиняється. Метою гри є загнати кульку в один із спеціальних отворів – виходів. Кулька провалюється в отвір, якщо він зустрічається на його шляху (кулька не повинна зупинятися в отворі).

Спочатку кулька знаходиться у лівому верхньому кутку лабіринту. Гарантується, що рішення існує і верхній лівий кут не зайнятий перешкодою або отвором.

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

У першому рядку вхідного потоку записані числа \(N\) та \(M\) – розміри лабіринту (цілі додатні числа, що не перевищують 100).

Потім йде \(N\) рядків по \(M\) чисел у кожному – описі лабіринту. Число 0 в описі означає вільне місце, число 1 – перешкода, число 2 – отвір.

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

Виведіть однину – мінімальну кількість нахилів, які необхідно зробити, щоб кулька залишила лабіринт через один з отворів.

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

4 5
0 0 0 0 1
0 1 1 0 2
0 2 1 0 0
0 0 1 0 0

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

3