У далекому королівстві жила принцеса, яка мала чарівну сітку розміром $N \times N$. Кожна клітинка сітки була або червоною, або синьою. Клітинка $(i,j)$ була червоною, якщо $c_{i,j} = R$, і синьою, якщо $c_{i,j} = B$.

Принцеса мала два завдання:

1. Вона повинна мати можливість пройти з лівого верхнього кута сітки $(1,1)$ до правого нижнього кута $(N,N)$, рухаючись лише через червоні або пурпурові клітинки.
2. Вона повинна мати можливість пройти з правого верхнього кута $(1,N)$ до лівого нижнього кута $(N,1)$, рухаючись лише через сині або пурпурові клітинки.

Принцеса може перетворити деякі клітинки на пурпурові, щоб задовольнити ці умови. Пурпурова клітинка дозволяє проходити через неї як червоним, так і синім шляхом.

Допоможіть принцесі знайти мінімальну кількість клітинок, які потрібно перетворити на пурпурові, щоб задовольнити обидві умови одночасно.

Input Specification

Вхідні дані подаються зі стандартного вводу у наступному форматі:

Перша строка містить одне ціле число $N$ $(3 \leq N \leq 500)$ --- розмір сітки.

Кожна з наступних $N$ строк містить $N$ символів $c_{i,j}$, де кожен символ є 'R' або 'B'.

Output Specification

Виведіть мінімальну кількість клітинок, які потрібно перетворити на пурпурові, щоб задовольнити обидві умови.

Sample Input 1

5
RBRBB
RBRRR
RRRBR
RBBRB
BBRBR

Sample Output 1

3

Sample Input 2

5
RBBBB
BBBBB
BBBBB
BBBBB
BBBBR

Sample Output 2

7