Битва титанів#380
Сашко захоплюється програмуванням комп'ютерних ігор. Ось уже три дні він пише нову гру для мобільного телефону під назвою Битва титанів. Героями гри є олов'яні солдатики. Як прототип для опису дій олов'яного солдатика Сашко взяв шахову туру.
Шахова тура — це фігура, яка може переміщуватись на довільну кількість клітин по вертикалі або горизонталі. Тури не можуть переміщуватись крізь перешкоди. Завдання — обчислити максимальну кількість тур, які можна поставити на дошці так, щоб жодні дві не били одна одну. Це означає, що конфігурація правильна, якщо жодні дві тури не знаходяться на одній горизонталі або вертикалі в межах видимості одна одної.
Наступний приклад показує п'ять зображень. Перше зображення — порожнє, друге й третє показують правильні конфігурації, а четвертий і п'ятий малюнки — приклади неправильних конфігурацій.
Допоможіть Сашку якомога швидше завершити програму та порахуйте максимальну кількість тур для заданої конфігурації дошки.
У першому рядку вхідного файлу міститься ціле число — розмір дошки, що не перевищує . Наступні рядки містять опис шахової дошки, де символ '.' позначає порожню клітинку, а велика літера 'X' — перешкоду. Пропусків у вхідному файлі немає.
Виведіть максимальну кількість тур для правильної конфігурації дошки.
Приклад 1