#### Statement

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
*s*and_{i}*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 ≤ |*s*| ≤ 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

#### Example output:

1 4 3 8 6 9 6 9 3 6

#### Time and memory limit:

- 1 second
- 256MB

**Problem source:**
SPOJ