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.
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.
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.