Черв'яки
Біологи досліджують певний цікавий вид черв'яків. Кожен черв'як може бути описаний як рядок клітин різних типів. Коли черв'як народжується, він складається лише з однієї клітини. Щодня рівно 1 клітина черв'яка розростається і перетворюється на 2 клітини. Визначити вік такого черв'яка досить просто: він на одиницю менший за кількість клітин, які має черв'як.
Під час росту черв'яка клітина не перетворюється на будь-які 2 довільні клітини; кожен черв'як має набір "правил росту" (закодованих у його ДНК), яких він дотримується. Правило росту може бути виражене як A => BC, де A, B і C - великі літери (від A до T), що представляють різні типи клітин черв'яка. Правило A => BC означає, що за один день будь-яка окрема клітина A може вирости в 2 сусідні клітини BC, у такому порядку. Зверніть увагу, що правило I => JK відрізняється від правила I => KJ. Різні черв'яки можуть мати різний набір правил росту.
Черв'яки тепер збили вчених з пантелику. Через якусь невідому причину деякі черв'яки мутували в новий вид. Цей новий вид черв'яків має ті ж самі властивості, за винятком того, що під час його росту кілька частин його тіла можуть рости одночасно. Тобто, щодня будь-яка (принаймні одна, максимум всі) з його клітин може рости; кожна клітина, що росте, виросте рівно в 2 клітини (дотримуючись правил росту, схожих на їхніх старших родичів).
В результаті мутації вже не так просто визначити вік черв'яка. Насправді, точний вік деяких черв'яків визначити неможливо. Як простий приклад, якщо черв'як має правила росту: A => BC, B => AC, C => AB, і поточна структура клітин черв'яка - ACAB, черв'як може бути або 2, або 3 дні ( A => BC => ACAB, або A => BC => ACC => ACAB). Ваше завдання - визначити наймолодший можливий вік будь-якого даного мутованого черв'яка.
Вхідні дані
У вхідних даних буде кілька черв'яків для дослідження. Дані кожного черв'яка починаються з цілого числа N (1 <= N <= 80), кількості правил росту. Наступні N рядків містять по 3 великі літери (від A до T), що представляють правило росту для поточного черв'яка. Перша клітина може вирости в (і бути заміненою) 2 і 3 клітинами, у порядку, під час процесу росту. Тобто, рядок:
ABC
означає, що A => BC є правилом росту для поточного черв'яка.
Наступний (і останній) рядок кожного набору даних черв'яка містить рядок великих літер (від A до T). Цей рядок представляє поточну структуру клітин черв'яка. Кожен черв'як у вхідних даних матиме принаймні 1 і не більше 50 клітин.
Останній черв'як буде слідувати за рядком з однією цифрою 0.
Вихідні дані
Для кожного черв'яка, якщо черв'як може бути вирощений у дану послідовність клітин з даним набором правил росту (починаючи з будь-якої довільної однієї клітини), то виведіть мінімальний вік, у днях, черв'яка, як ціле число в окремому рядку. Якщо черв'як не може бути вирощений у дану послідовність клітин з даним набором правил (починаючи з будь-якої довільної однієї клітини), то просто виведіть число '-1' в окремому рядку. Не друкуйте порожніх рядків між вихідними даними.