# Shuffling Strings

Time Limit: 10 Seconds Memory Limit: 131072 KB

Suppose S_{1} and S_{2} are two strings of size n consisting of characters A through H (capital letters). We plan to perform the following step several times to produce a given string S. In each step we shuffle S_{1} and S_{2} to get string S_{12}. Indeed, S_{12} is obtained by scanning S_{1} and S_{2} from left to right and putting their characters alternatively in S_{12} from left to right. The shuffling operation always starts with the leftmost character of S_{2}. After this operation, we set S_{1} and S_{2} to be the first half and the second half of S_{12}, respectively. For instance, if S_{1}=ABCHAD and S_{2}=DEFDAC, then S_{12}=DAEBFCDHAACD, and for the next step S_{1}=DAEBFC and S_{2}=DHAACD. For the given string S of size 2n, the goal is to determine whether S_{12}=S at some step.

## Input

There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers 0ā¤nā¤100 which is the length of S_{1} and S_{2}. The remainder of each test case consists of three lines. The first and the second lines contain strings S_{1} and S_{2} with size n, respectively, and the last line contains string S with size 2n. The input terminates with ā0ā which should not be processed.

## Output

For each test case, output -1 if S is not reachable. Otherwise, output the minimum number of steps to reach S.

To make your life easier, we inform you that **the output is not greater than 50 for the given input.**

## Sample Input

4 AHAH HAHA HHAAAAHH 3 CDE CDE EEDDCC 0

## Sample Output

2 -1Submit

Source: 11th Iran Nationwide Internet Contest