Moloco의 Tap Titanz (Hard)

Moloco 직원 중에는 Tap Titanz 같은 클리커 게임을 즐기는 사람이 있다.

Tap Titanz는 각 칸이 검은색이거나 흰색인 $n \times n$ 판에서 진행한다. 변을 맞대고 있는 두 칸은 인접하다고 한다. 같은 색 칸만 거쳐 인접한 칸을 따라 한 칸에서 다른 칸까지 갈 수 있으면 두 칸은 연결되어 있다고 한다. 연결된 두 칸의 색은 항상 같다.

플레이어가 칸 하나를 누르면 그 칸의 색이 반대 색으로 바뀌고, 그 칸과 같은 색이던 인접한 칸, 다시 그 칸과 같은 색이던 인접한 칸도 차례로 색이 바뀐다. 즉, 누른 칸과 그 칸에 연결된 모든 칸의 색이 동시에 반대 색으로 바뀐다.

모든 칸의 색이 같아지면, 그러니까 전부 검은색이거나 전부 흰색이 되면 게임이 끝난다. 누르는 횟수를 최소로 하는 것이 목표이다.

첫째 줄에 정수 $n$이 주어진다. ($1 \le n \le 25$)

다음 $n$개의 줄에 판의 각 행이 위에서부터 순서대로 주어진다. 각 줄은 길이가 $n$인 문자열이고, 'B'는 검은색 칸, 'W'는 흰색 칸을 뜻한다.

모든 칸의 색을 같게 만들기 위해 눌러야 하는 최소 횟수를 한 줄에 출력한다.