Перемішування рядків
Припустимо, що S_1 та S_2 — це два рядки довжини n, що складаються з символів від A до H (великі літери). Ми плануємо виконати наступний крок кілька разів, щоб отримати заданий рядок S. На кожному кроці ми перемішуємо S_1 та S_2, щоб отримати рядок 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 для даного вводу.