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

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

hide comments
2018-04-16 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.
what do I win?
2018-02-02 08:54:47
@abhishek_19 operations can be performed at most once. Read the question properly.
2018-02-01 14:46:41 zimpha
@shubham_001 @abhishek_19 Maybe you both mistake substring with subsequence.
2018-01-31 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
2018-01-30 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...
2018-01-27 07:49:51
"teretwer" answer to this string should be 7 . Answer is 'tereret' this is the longest substring after changes.
Similarly many strings have wrong answers in the output.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.