A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left.
Chiaki has a string s and she can perform the following operation at most once:
- choose two integer i and j (1 ≤ i, j ≤ |s|),
- swap si and sj.
Chiaki would like to know the longest palindromic substring of string after the operation.
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case the first line contains a non-empty string s (1 ≤ |s| ≤ 106) consisting of lowercase and uppercase letters.
It is guaranteed that the sum of all |s| does not exceed 106.
For each test case, output an integer denoting the answer.
10 a xxxx ssfs aaabbacaa missimxx ababababgg dfsfsdgdg asdsasdswe chiaki teretwer
1 4 3 8 6 9 6 9 3 6
Time and memory limit:
- 1 second
Problem source: SPOJ