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