Перемішування рядків#6901
Припустимо, що S_1 та S_2 — це два рядки довжини , що складаються з символів від до (великі літери). Ми плануємо виконати наступний крок кілька разів, щоб отримати заданий рядок . На кожному кроці ми перемішуємо 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_{12} = S на якомусь кроці.
Вхід містить кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить невід'ємне ціле число 0 \leq n \leq 100, яке є довжиною S_1 та S_2. Решта кожного тестового випадку складається з трьох рядків. Перший та другий рядки містять рядки S_1 та S_2 довжини , відповідно, а останній рядок містить рядок довжини . Вхід завершується "", який не слід обробляти.
Для кожного тестового випадку виведіть , якщо недосяжний. В іншому випадку виведіть мінімальну кількість кроків для досягнення . Щоб полегшити ваше завдання, ми повідомляємо, що вихід не перевищує для даного вводу.
Приклад 1