Круглі слова
Після недавнього кінця світу Азамат нарешті опанував алгоритм знаходження найбільшої спільної підпослідовності (LCS - longest common subsequence). Йому стало цікаво, як цей алгоритм працюватиме, якщо слова будуть круглими.
У круглих словах не має значення, з якого символу вони починаються і в якому напрямку читаються. Наприклад, слово algorithm можна прочитати як rithmalgo або як oglamhtir.
Якщо для слів algorithm і grammar у звичайному вигляді довжина найбільшої спільної підпослідовності дорівнює 3 (слово grm), то для круглого варіанту цих же слів довжина найбільшої спільної підпослідовності дорівнює 4 (слово grma).
Азамат швидко зрозумів, що відомий алгоритм не може дати правильну відповідь для круглих слів. Напишіть програму, яка це зробить.
Вхідні дані
У двох рядках подано по одному слову. Слова не порожні, і довжина кожного не перевищує 2000 символів.
Вихідні дані
Виведіть одне ціле число — довжину найбільшої спільної підпослідовності заданих круглих слів.