쿼드트리

이진 이미지(binary image)는 검은색과 흰색, 오직 두 가지 색의 픽셀로만 이루어진 이미지입니다. 모든 이진 이미지는 $N \times N$ 픽셀로 구성되며, $N$은 2의 거듭제곱이고 $N \le 1024$입니다. 두 이진 이미지 $I_1$과 $I_2$가 주어졌을 때, 두 이미지의 교집합 $I_3$은 다음과 같이 정의되는 새로운 이진 이미지입니다. $I_3$의 어떤 픽셀이 검은색인 것은, 그 픽셀이 $I_1$과 $I_2$ 양쪽 모두에서 검은색일 때에 한합니다.

쿼드트리(quadtree)는 이진 이미지를 표현하는 뿌리 있는 트리입니다. 루트는 이미지 전체에 대응합니다. 이미지가 한 가지 색(검은색 또는 흰색)으로만 이루어져 있으면, 쿼드트리는 루트 하나만 가지며 검은색이면 'b', 흰색이면 'w'로 표시합니다. 그렇지 않으면 루트를 'i'('internal', 내부 노드)로 표시하고, 이미지를 똑같은 크기의 네 부분으로 나눕니다(그림 참고). 나뉜 네 부분 역시 각각 이진 이미지입니다. 이 네 부분 이미지 각각에 대해 같은 절차를 반복합니다. 어떤 부분 이미지가 한 가지 색이면 그에 따라 'b' 또는 'w'로 표시하고, 그렇지 않으면 다시 네 개로 나눕니다. 이 절차는 픽셀 단위에 이를 때까지 반복될 수 있습니다.

부모 노드의 네 자식에 붙이는 번호는 아래 그림과 같습니다. 쿼드트리 표현에서 1번 사분면이 가장 왼쪽 자식, 4번 사분면이 가장 오른쪽 자식이 됩니다. 같은 규칙이 트리의 모든 레벨에 재귀적으로 적용됩니다.

이미지 1	이미지 2	이미지 3

쿼드트리의 전위 순회(pre-order traversal)에서는 먼저 루트를 방문하고, 이어서 위의 순서에 따라 (존재한다면) 네 자식을 방문합니다. 네 자식 각각에 대해서도 그 자식을 해당 부분 트리의 루트로 보고 같은 규칙을 재귀적으로 적용합니다.

두 이미지에 대응하는 두 쿼드트리의 전위 순회 문자열이 주어질 때, 두 이미지의 교집합에 대응하는 쿼드트리에 포함된 노드의 개수를 구하는 것이 여러분의 과제입니다. 교집합 이미지의 쿼드트리 역시 위와 같은 규칙으로 만들어지므로, 네 사분면이 모두 같은 색이 되는 영역은 하나의 잎 노드로 합쳐집니다.

표준 입력에서 다음 형식으로 입력을 읽습니다. 첫 번째 줄에는 이미지의 크기 $N$을 나타내는 양의 정수가 주어집니다. 다음 두 줄에는 각 이미지의 쿼드트리를 전위 순회한 문자열이 한 줄에 하나씩 주어집니다. 각 문자열은 해당 이미지 쿼드트리의 전위 순회를 나타냅니다. 전위 순회 문자열에는 세 가지 문자만 나타날 수 있습니다. 내부 노드를 뜻하는 'i', 검은색 사분면을 뜻하는 'b', 흰색 사분면을 뜻하는 'w'입니다.

표준 출력에 한 줄을 출력합니다. 교집합에 대응하는 쿼드트리의 전체 노드 개수(잎 노드 + 내부 노드)를 출력하면 됩니다.