Подвійна проблема
Аліса Кетрін Морріс та її сестра Ірен Барбара часто обмінюються електронними листами. Щоб зберегти свою переписку конфіденційною, вони шифрують свої повідомлення у два етапи. Спочатку видаляють усі неалфавітні символи і переводять усі літери у верхній регістр. Потім: 1) замінюють кожну літеру на літеру, що знаходиться на s позицій далі в алфавіті (1 ≤ s ≤ 25) — це називається зсувом на s; 2) ділять результат першого кроку на групи по m літер і перевертають літери в кожній групі (5 ≤ m ≤ 20). Якщо довжина повідомлення не ділиться на m, тоді останні k (менше ніж m) літер перевертаються. Наприклад, якщо s = 2 і m = 6, і відкритий текст був
Meet me in St. Louis, Louis.
після видалення небажаних символів і зміни на верхній регістр ми отримуємо
MEETMEINSTLOUISLOUIS
Це називається модифікованим відкритим текстом. Потім ми зсуваємо кожну літеру на 2 (Y замінюється на A, а Z на B), отримуючи проміжний результат:
OGGVOGKPUVNQWKUNQWKU
І нарешті перевертаємо кожну групу з 6 літер:
GOVGGOQNVUPKWQNUKWUK
Зверніть увагу, що останні дві літери утворюють останню перевернуту групу. Як зазвичай, ми записуємо результат у групах по 5 літер. Отже, шифротекст буде:
GOVGG OQNVU PKWQN UKWUK
На жаль, не так вже й важко знайти значення для s і m, коли шифротекст перехоплено. Це стає ще легше, якщо ви знаєте підказку, яка є словом у модифікованому відкритому тексті. У наведеному прикладі, LOUIS буде підказкою. Ваше завдання — знайти s і m, коли вам надано шифротекст і підказку.
Вхідні дані
Вхідні дані складаються з кількох задач. Перша строка містить додатне ціле число, яке вказує кількість задач. Вхідні дані для кожної задачі складаються з кількох строк. Перша строка для задачі містить ціле число n (20 ≤ n ≤ 500), яке дорівнює кількості символів у шифротексті. Наступні строки містять шифротекст, всі у верхньому регістрі у групах по 5 літер, розділених одним пробілом. (Остання група літер може містити менше ніж 5 літер.) На кожній строкі буде 10 груп літер, за винятком, можливо, останньої строки шифротексту. Вхідна строка, що слідує за останньою строкою шифротексту, містить підказку; одне слово, що складається з від 4 до 10 (включно) літер у верхньому регістрі.
Вихідні дані
Вихідні дані повинні містити два цілі числа, s і m на одній строкі, розділені одним пробілом, що вказують ключ шифрування, який створює підказку, де s — це зсув, а m — розмір перевернутої групи. Якщо існує більше одного рішення, виведіть те, у якого найменше s. Якщо є більше одного з однаковим s, виведіть те, у якого найменше m. Якщо таких s і m не існує, виведіть повідомлення "Crib is not encrypted.".