Браслети
Нарешті, Мегамозок розробив ідеальний план, щоб здолати свого заклятого ворога, Метро Мена! Він створив пару кругових силових браслетів, які потрібно носити на лівому та правому зап'ястях. На кожному браслеті викарбувано послідовність магічних гліфів (тобто символів); кожен активований гліф збільшує силу Мегамозка на потужність одного грізлі!
Однак є одна умова: браслети працюють лише тоді, коли підпослідовності гліфів, активовані на кожному браслеті, ідентичні. Наприклад, якщо брати пару браслетів, гліфи яких представлені рядками "metrocity" та "kryptonite", то оптимальна активація гліфів дасть Мегамозку силу 10 грізлі:
Рисунок 1: Силові браслети Мегамозка
На першому браслеті активуються літери "etoty" за годинниковою стрілкою; ті ж самі літери активуються проти годинникової стрілки на другому браслеті. Загалом, порядок літер важливий, але орієнтація активованої підпослідовності на кожному браслеті (тобто за годинниковою стрілкою чи проти) може бути однаковою або різною — і не забувайте, що браслети є круговими!
Допоможіть Мегамозку перемогти Метро Мена, визначивши оптимальні підпослідовності гліфів, необхідні для активації його браслетів.
Вхідні дані
Вхідний файл міститиме не більше 100 тестових випадків (включаючи не більше 5 "великих" тестових випадків). Кожен тестовий випадок задається одним рядком, що містить пару рядків s та t, розділених пробілом, які відповідають послідовностям гліфів на лівому та правому силових браслетах Мегамозка, відповідно. Кожен рядок складатиметься лише з малих літер ('a'-'z'). Довжина кожного вхідного рядка буде від 1 до 100 символів включно, за винятком великих тестових випадків, де довжина кожного вхідного рядка буде від 1 до 1500 символів включно.
Вихідні дані
Для кожного вхідного тестового випадку виведіть максимальну потужність (в одиницях грізлі), яку Мегамозок зможе досягти, активуючи гліфи на своїх браслетах.