Почини пруд
Креветочная ферма использует прямоугольный пруд, построенный в виде сетки с 2N рядами и 2N+1 столбцами квадратных ячеек, для заданного целого числа N. Каждая сторона ячейки имеет длину один метр. В пруду ровно (2N-1)×N барьеров длиной два метра, которые используются для временной изоляции меньших участков внутри пруда для разведения различных видов креветок. Барьеры имеют свои средние точки, зафиксированные точно в целочисленных координатах (a, b), для всех 0 < a < 2N и 0 < b < 2N+1, где и a, и b либо нечетные, либо четные. Каждый барьер может быть повернут вокруг своей средней точки для изменения конфигурации пруда; однако, при повороте барьер переключается только между двумя возможными положениями, всегда параллельными сторонам пруда, вертикально или горизонтально. Левая часть рисунка ниже показывает конфигурацию пруда при N = 3.
В конце каждого сезона пруд закрывается для обслуживания и очистки. Затем его необходимо переконфигурировать так, чтобы специальная машина могла подмести дно пруда. Машина начинает свою работу с верхней левой ячейки и должна пройти через каждую ячейку ровно один раз, заканчивая в нижней левой ячейке. Правая часть рисунка показывает одну из таких переконфигураций, где шесть барьеров были переключены. Однако в этом примере было бы достаточно четырех переключений барьеров.
Ваша задача — написать программу, которая, получив конфигурацию пруда, определяет минимальное количество переключений барьеров, необходимых для переконфигурации пруда, как указано выше. Всегда существует хотя бы один возможный способ переконфигурации пруда, как указано.
Входные данные
Каждый тестовый случай описывается с использованием нескольких строк. Первая строка содержит целое число N, указывающее, что пруд имеет 2N рядов и 2N+1 столбцов (1 ≤ N ≤ 300). Каждая из следующих 2N-1 строк содержит строку из N символов, описывающих ориентацию барьеров. В i-й строке j-й символ указывает ориентацию барьера, средняя точка которого находится в координатах (i, 2j-1), если i нечетное, или (i, 2j), если i четное, для i = 1, 2, ..., 2N-1 и j = 1, 2, ..., N. Символ — это заглавная буква 'V', если ориентация вертикальная, или заглавная буква 'H', если она горизонтальная.
Выходные данные
Для каждого тестового случая выведите строку с целым числом, представляющим минимальное количество переключений барьеров, необходимых для переконфигурации пруда, как указано.