E :: Shuffling Strings

Time Limit: 10 Seconds    Memory Limit: 131072 KB

Suppose S₁ and S₂ 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₁ and S₂ to get string S₁₂. Indeed, S₁₂ is obtained by scanning S₁ and S₂ from left to right and putting their characters alternatively in S₁₂ from left to right. The shuffling operation always starts with the leftmost character of S₂. After this operation, we set S₁ and S₂ to be the first half and the second half of S₁₂, respectively. For instance, if S₁=ABCHAD and S₂=DEFDAC, then S₁₂=DAEBFCDHAACD, and for the next step S₁=DAEBFC and S₂=DHAACD. For the given string S of size 2n, the goal is to determine whether S₁₂=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₁ and S₂. The remainder of each test case consists of three lines. The first and the second lines contain strings S₁ and S₂ 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
-1

Submit

Source: 11th Iran Nationwide Internet Contest