Hidden Palindrome

Given a word of at most 40 lowercase letters, find the longest palindromic subsequence obtainable by deleting letters from the front and back.

Medium4Dynamic programmingStringIntervalsRecursionInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

A palindrome reads the same forwards and backwards. For example, mom and anna are palindromes. A word with a single letter, such as a, is also a palindrome.

You are given one word. You can delete letters from the front of the word and from the back of the word. Find the greatest length you can leave behind while the remaining part is a palindrome. That length is the length of the longest palindrome contained in the word.

Input

The first line contains a string of lowercase English letters. Its length is at least 1 and at most 40.

Output

Print the number of letters in the longest palindrome contained in the given word.