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
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 