SPOJ in Gyumri

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

Examples