Как вы уже знаете, Вупсень очень любит давать задачи на поиск наибольшей общей подпоследовательности, а Пупсень очень любит давать задачи на поиск наибольшей правильной скобочной подпоследовательности. Лунтик решил обрадовать своих друзей и подарить им на новый год две строки. Конечно же, Вупсень и Пупсень сразу, не посмотрев на строки, захотели дать задачу на поиск наибольшей общей правильной скобочной подпоследовательности, но не тут то было: в этих строках не было скобок. Лунтик понимал, что если Вупсень и Пупсень увидят решения с битсетами, то будут грустить, и весь праздник испортится, поэтому он придумал другую задачу: найдите длину наибольшего общего подпалиндрома.
Подпалиндромом называется такая попоследовательность строки, которая читается справа налево также, как и слева направо.
Формат входный данных
В первой строке дана строка s, во второй строке строка t, состоящие из строчных латинских букв. 1 <= |s|, |t| <= 50.
Формат выходных данных
Выведите одно целое число n - длину наибольшей общей подпоследовательности, являющейся палиндромом.
Примеры
|
Ввод |
Вывод |
|
mem
kek
|
1 |
|
acab
abca
|
3 |
(с) Буков Антон, 11и