Фишки на доске
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
board.in
вывод
board.out

У Влада есть клетчатая доска n × n. Некоторые клетки этой доски покрашены в белый, а некоторые в чёрный цвет. Известно, что все клетки первого и последнего столбцов покрашены в белый цвет.

В первом столбце расположены n фишек по одной в каждом ряду. За один ход Влад может переместить каждую из фишек в одном из направлений вверх, вниз, влево, вправо или оставить фишку на месте. Фишку нельзя перемещать на чёрную клетку, и нельзя ставить две фишки в одну клетку. Все фишки перемещаются одновременно, поэтому Влад может переместить фишку в клетку, в которой на прошлом ходу была другая фишка, если она в свою очередь перемещается.

Цель игры — как можно скорее переместить все фишки в правый столбец. Влад научился делать это достаточно быстро, но не уверен, что быстрее нельзя. Определите минимальное количество ходов, которое необходимо для того, чтобы переместить все фишки из левого в правый столбец поля.

Входные данные

В первой строке входных данных содержится одно целое число n (3 ≤ n ≤ 25). Далее n строк содержат описание игровой доски. Белые клетки обзначены символом W, а чёрные — B.

Гарантируется, что всегда можно переместить все фишки из левого в правый столбец поля.

Выходные данные

Выведите одно целое число, равное минимальному числу ходов.

Примеры

Входные данные
5
WWWWW
WBWWW
WWWBW
WWBWW
WWWWW
Выходные данные
6
Входные данные
5
WBWWW
WBWWW
WBWWW
WBBBW
WWWWW
Выходные данные
8