시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB73360.000%

문제

Eric is a cool kid who just learned that a palindrome is a string that reads the same forward and backward. Recently, he found a string consisting of $n$ lowercase English letters. He immediately started looking for palindromic substrings in it (a substring is a contiguous sequence of characters within a string). He soon realized that the string did not contain very long palindromic substrings.

Eric wants to improve the situation by performing exactly one swap of two letters in the string (the letters must be at different positions). What is the length of the longest palindromic substring that can be obtained after Eric performs exactly one swap?

입력

The input consists of a single string containing at least $2$ and at most $5\, 000$ lowercase English letters (a-z).

출력

Output a single integer, the length of the longest palindromic substring that Eric can obtain after exactly one swap.

예제 입력 1

ccbaada

예제 출력 1

5

Eric can swap the first c with the first a, i.e., ccbaada. The resulting string is acbcada, which has a palindromic substring of length $5$: acbca.

예제 입력 2

ab

예제 출력 2

1