Перемешивание строк
Предположим, что S_1 и S_2 — это две строки длины n, состоящие из символов от A до H (заглавные буквы). Мы собираемся выполнить следующий шаг несколько раз, чтобы получить заданную строку S. На каждом шаге мы перемешиваем S_1 и S_2, чтобы получить строку S_{12}. Строка S_{12} формируется путем сканирования S_1 и S_2 слева направо и чередования их символов в S_{12} слева направо.
Операция перемешивания всегда начинается с самого левого символа S_2. После этой операции мы устанавливаем S_1 и S_2 как первую и вторую половины S_{12} соответственно. Например, если S_1 = ABCHAD и S_2 = DEFDAC, то S_{12} = DAEBFCDHAACD, и для следующего шага S_1 = DAEBFC и S_2 = DHAACD. Для данной строки S длины 2n цель состоит в том, чтобы определить, равно ли S_{12} = S на каком-либо шаге.
Входные данные
Входные данные содержат несколько тестов. Каждый тест начинается с строки, содержащей неотрицательное целое число 0 ≤ n ≤ 100, которое является длиной S_1 и S_2. Остальная часть каждого теста состоит из трех строк. Первая и вторая строки содержат строки S_1 и S_2 длины n соответственно, а последняя строка содержит строку S длины 2n. Ввод завершается строкой "0", которая не должна обрабатываться.
Выходные данные
Для каждого теста выведите -1, если S недостижима. В противном случае выведите минимальное количество шагов для достижения S. Чтобы облегчить вам задачу, мы сообщаем, что вывод не превышает 50 для данного ввода.