패널 정렬

탐험가 헨리 넬슨이 오래된 건물 앞에 도착했다. 호기심에 안으로 들어가려 했지만, 입구는 낯선 잠금 장치로 막혀 있었다.

입구 앞에는 검은색과 흰색 패널이 일직선 위에 같은 간격으로 놓여 있고, 암호문이 붙은 기계 한 대가 있다. 한참 만에 읽어낸 암호문의 내용은 이렇다. 패널을 정해진 순서로 다시 배열하면 입구가 열리며, 순서를 바꾸려면 이 기계를 써야 한다.

기계로 할 수 있는 일은 패널 두 개를 골라 서로 맞바꾸는 것뿐이다. 한 번의 교환은 다음 세 단계로 이뤄진다.

• 기계를 패널 하나로 옮겨 그 패널에 표시를 남긴다.
• 기계를 다른 패널로 옮겨 그 패널에도 표시를 남긴다.
• 기계의 특수 스위치를 켜면 표시된 두 패널이 자리를 바꾼다.

패널 세 개 이상에 동시에 표시를 남길 수는 없다. 교환이 끝나면 표시는 모두 지워진다.

기계가 워낙 무거워서 헨리는 기계를 필요 이상으로 옮기고 싶지 않다. 이웃한 패널 사이로 기계를 옮기는 비용을 1이라고 할 때, 패널을 목표 순서로 만드는 데 드는 최소 비용을 구하라. 기계의 처음 위치는 마음대로 정할 수 있고, 그 위치까지 기계를 옮기는 비용은 세지 않는다.

입력은 여러 개의 데이터 집합으로 이뤄진다.

데이터 집합 하나는 세 줄이다. 첫째 줄에는 패널의 개수 $N$이 주어진다 ($2 \le N \le 16$). 둘째 줄과 셋째 줄에는 각각 $N$개의 문자가 주어지며, 차례로 패널의 처음 순서와 목표 순서를 나타낸다. 각 문자는 검은색을 뜻하는 B 또는 흰색을 뜻하는 W이다. 같은 색 패널은 서로 구분하지 않는다.

입력의 마지막 줄에는 0 하나만 주어진다. 데이터 집합은 15개 이하이다.

각 데이터 집합마다 최소 비용을 한 줄에 출력한다.

처음 순서에서 목표 순서로 바꾸는 방법이 적어도 하나 있다고 가정해도 된다.