На прямокутному полі ~N{\times}M~ клітинок у лівому верхньому кутку стоїть фішка. Ця кутова клітинка гарантовано вільна (не замінована); абсолютно кожна інша клітинка поля може бути хоч вільною, хоч замінованою. Гра полягає в тому, що два гравці поперемінно рухають згадану фішку на якусь кількість клітинок або праворуч, або донизу (кожен гравець сам вирішує, в якому з цих двох напрямків і на скільки клітинок рухати; не можна ні лишати фішку на місці, ні ставати нею в заміновану клітинку, ні перестрибувати нею через заміновану клітинку). Програє той, хто не може нікуди походити (і знизу, і праворуч або край поля, або міна). Відповідно, його суперник виграє.

Напишіть програму, яка визначатиме, хто виграє при правильній грі обох гравців. Іншими словами, хто може забезпечити собі виграш, хоч би як не грав інший.

Вхідні дані

Перший рядок містить два цілі числа ~N~ та ~M~, розділені одним пропуском (пробілом) – спочатку кількість рядків, потім кількість стовпчиків. Обидва ці значення у межах від 1 до 12.

Далі йдуть ~N~ рядків, що задають мінне поле. Кожен з них містить рівно по ~M~ символів . (позначає вільну клітинку) та/або * (позначає заміновану клітинку). Ці символи йдуть без роздільників, і кожен з цих ~N~ рядків містить лише ці символи та переведення рядка наприкінці.

Результати

Єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий).

Приклади

Вхід

2 4
....
.**.

Результат

1

Вхід

1 1
.

Результат

2

Примітки

У першому прикладі, перший гравець може, наприклад, піти на одну клітинку вниз, після чого другому не буде куди йти, і він програє. Якби перший гравець сильно помилився і пішов на першому кроці на три клітинки праворуч, то другий пішов би на одну вниз і виграв. Але це значило б, що перший грає неправильно, а питають про ситуацію правильної гри обох гравців.

У другому прикладі, першому гравцю відразу ж нема куди йти, і він негайно програє (відповідно, виграє другий гравець). Звісно, з точки зору загальнолюдських уявлень про справедливість це якась дуже нечесна гра... Але вже яка є, описані в умові задачі обмеження формально дотримані.