Just a Palindrome

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 si and sj.

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| ≤ 106) consisting of lowercase and uppercase letters.

It is guaranteed that the sum of all |s| does not exceed 106.

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

s