Реставратор изучает старинную надпись, представленную строкой s из строчных латинских букв. Часть символов повреждена временем, и он хочет выбрать из надписи как можно больше букв так, чтобы выбранные буквы шли в том же порядке, что и в исходной строке, но не обязательно подряд, и образовывали палиндром.

Иными словами, требуется найти длину самой длинной палиндромной подпоследовательности строки s.

Подпоследовательностью строки называется последовательность символов, которую можно получить удалением некоторых символов без изменения порядка оставшихся.

Входные данные

В единственной строке задана непустая строка s из строчных латинских букв.

Выходные данные

Выведите одно целое число — длину самой длинной палиндромной подпоследовательности строки s.

Ограничения

1 <= |s| <= 1000

Примеры

Пример 1

Входные данные

a

Выходные данные

1

Пример 2

Входные данные

ab

Выходные данные

1