QuadTrees

A binary image is an image containing pixels colored by only two colors, either black or white. Each binary image is composed of $N \times N$ pixels, where $N$ is a power of 2 and $N \le 1024$. Given two binary images $I_1$ and $I_2$, their intersection is a new binary image $I_3$ such that a pixel in $I_3$ is black if and only if it is black in both $I_1$ and $I_2$.

A quadtree is a rooted tree that represents a binary image. The root corresponds to the whole image. If the image is one color (black or white), the quadtree contains only the root, labeled 'b' if it is black and 'w' if it is white. Otherwise, the root is labeled 'i' (standing for "internal"), and the image is split into 4 equal parts (see figure), which are themselves binary images. The same procedure is applied to each of these subimages: if a subimage is one color it is labeled 'b' or 'w' accordingly, otherwise it is split into 4 sub-subimages. This procedure may be repeated down to the pixel level.

The numbering of the children of a parent node is illustrated in the following figure. Subquadrant 1 is placed as the left-most child and subquadrant 4 as the right-most child in the quadtree representation. The same rule is followed recursively for all levels of the quadtree.

Image 1	Image 2	Image 3

In the pre-order traversal of a quadtree, we first visit the root and then its 4 children (if they exist) following the ordering above. For each child, the same rule applies recursively, taking that child as the root of its subtree.

Your task is, given the pre-order traversals of two quadtrees (corresponding to two images), to find the number of nodes contained in the quadtree of their intersection. The quadtree of the intersection image is built by the same rule, so any region whose four subquadrants all become the same color collapses into a single leaf.

Read the input from standard input. The first line contains a positive integer $N$, the size of the images. The next two lines each contain the pre-order string of one image's quadtree (one string per line). Each string represents the pre-order traversal of the corresponding image's quadtree. Only three characters may appear: 'i' for an internal node, 'b' for a black quadrant, and 'w' for a white quadrant.

Print a single line containing the total number of nodes (leaves plus internal nodes) of the quadtree corresponding to the intersection.