Задачи
Битва титанов
Битва титанов
\includegraphics{https://static.e-olymp.com/content/ba/bad05ac543afe2c3b6ce4e43ede10b2d021f8646.jpg}
Саша увлекается программированием компьютерных игр. Вот уже три дня он пишет новую игру для сотового телефона под названием "Битва титанов". Героями игрушки являются оловянные солдатики. В качестве прототипа для описания действий оловянного солдатика Саша взял шахматную ладью.
Шахматная ладья - это фигура, которая может перемещаться на любое количество клеток по вертикали или горизонтали. Ладьи не могут перемещаться за препятствия. Задача - вычислить максимальное количество ладей, которые можно поставить на доске так, чтобы никакие две не били друг друга. Это означает, что конфигурация правильна при условии, что никакие две ладьи не находятся на одной горизонтали или вертикали в пределах видимости друг друга.
Следующий пример показывает пять изображений. Первое изображение является пустым, второе и третье изображения показывают правильные конфигурации, а четвертый и пятый рисунок - примеры неправильных конфигураций.
\includegraphics{https://static.e-olymp.com/content/f1/f1768d870e30f49c740f625adf1a2aa083e5b4c4.jpg}
Помогите Саше поскорее закончить программу и вычислите максимальное количество ладей на заданной конфигурации доски.
\InputFile
Во входном файле в первой строке содержится целое число - размер доски, не превышающий \textbf{4}. Последующие строки содержат описание шахматной доски, причем символ '\textbf{.}' указывает пустую клетку, а символ верхнего регистра '\textbf{X}' указывает препятствие. Во входном файле нет пробелов.
\OutputFile
Вывести максимальное количество ладей на правильной конфигурации доски.
Входные данные #1
4 .X.. .... XX.. ....
Выходные данные #1
5