A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left.

There're a string `s` and an operation defined on the string.

- choose two integer
`i`and`j`(1 ≤`i`,`j`≤ |`s`|). - swap
`s`_{i}and`s`_{j}.

You are given the string, and you can perform the operation once. Please find the longest palindromic substring of string after you perform the operation.

Input will consist of multiple test cases. Each test case contains exactly one line, which gives a non-empty string consisting of lowercase and uppercase letters. The length of the string will not be greater than 10^{5}.

For each test case, print a line containing the test case number (beginning with 1) followed by the length of the longest palindrome.

提交代码