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

hide comments
vss1996: 2018-02-02 08:54:47

@abhishek_19 operations can be performed at most once. Read the question properly.

zimpha: 2018-02-01 14:46:41

@shubham_001 @abhishek_19 Maybe you both mistake substring with subsequence.

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

cjmachado: 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...

abhishek_19: 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.


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