Shuffling Strings#6901
Suppose S_1 and S_2 are two strings of size consisting of characters through (capital letters). We plan to perform the following step several times to produce a given string . 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 of size , 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 integer 0 \leq n \leq 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 , respectively, and the last line contains string with size . The input terminates with "" which should not be processed.
For each test case, output if is not reachable. Otherwise, output the minimum number of steps to reach . To make your life easier, we inform you that the output is not greater than for the given input.
Example 1