Юный волшебник Айвен считает последовательность символов магической, если она является палиндромом (то есть читается одинаково как слева направо, так и справа налево). Айвену попалась в руки последовательность символов
s. Он хочет удалить из нее любое (возможно нулевое) количество символов, чтобы получить из нее самую длинную магическую подпоследовательность.
Определите длину самой длинной магической подпоследовательности, которую сможет получить Айвен.
Входные данные
Программа получает на вход последовательность символов
s (1<=
|s| <= 1000), состоящую из строчных английских букв.
Выходные данные
Выведите одно число - длину самой длинной магической подпоследовательности.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
bbbab
|
4
|