JUSTAPAL  Just a Palindrome
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 \le i, j \le s$).
 swap $s_i$ and $s_j$.
Chiaki would like to know the longest palindromic substring of string after the operation.
Input
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 nonempty string $s$ ($1 \le s \le 10^6$) consisting of lowercase and uppercase letters.
It is guaranteed that the sum of all $s$ does not exceed $10^6$.
Output
For each test case, output an integer denoting the answer.
Example
Input:
10 a xxxx ssfs aaabbacaa missimxx ababababgg dfsfsdgdg asdsasdswe chiaki teretwer
Output:
1 4 3 8 6 9 6 9 3 6
hide comments
charraster:
20180416 17:32:54
sparse bit vector for marking visited palindrome centers, 52 linkedlists walk from beginning in outer loop and from end in inner loop, eliminate visited beginnings from list. keep longest candidates in heap, when maximum shorter than longest print answer.


vss1996:
20180202 08:54:47
@abhishek_19 operations can be performed at most once. Read the question properly. 

zimpha:
20180201 14:46:41
@shubham_001 @abhishek_19 Maybe you both mistake substring with subsequence. 

shubham_001:
20180131 17:37:48
@abhishek_19 is quite right I think, in "teretwer" if we swap last t and last r , we have "tererwet" now ans is "tereret" which is of length 7 

cjmachado:
20180130 08:28:42
I think you didn't understand the at most one swap part... You can make a swap or no swaps at all and those are the only options. teretwer you swap the w for the first t.... weretter making a maximum palindrome of six characters > retter... 

abhishek_19:
20180127 07:49:51
"teretwer" answer to this string should be 7 . Answer is 'tereret' this is the longest substring after changes.

Added by:  zimpha 
Date:  20180121 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 