3626. Thinking-Bear's Necklace

单测试点时限: 2.0 秒

内存限制: 512 MB

Thinking-Bear gave a string of letters to the sister who admired in the heart. Sister looked at the string and said to Thinking-Bear: “I hope it is symmetrical”. Thinking-Bear decided to cut a continuous part from the original string and join to form a new necklace. A necklace is symmetrical if we can cut it into a palindrome.

Thinking-Bear can use magic. He can replace one letter to another letters. The magic can be used at most twice. Thinking-Bear want to know what’s the longest length of necklace he is able to capture. We assume that the length of the new necklace must be an odd number.

Note: This problem is different from the original Metropolitan problem in that the necklace being cut is joined to form a new necklace, instead of the remaining part.

输入

Th first line of the input is (), which stands for the number of test cases you need to solve.

Each test case contains a string , indicates the necklace. ().

Notice: can be . for all tests does not exceed .

输出

For each test case, output a number, meaning the longest length of symmetrical necklace he can capture.

样例

Input
1
abcdaaa
Output
7

提示

For the sample, he can replace one ltter to “abcbaaa”.

1 人解决,2 已尝试。

5 份提交通过,共有 11 份提交。

9.9 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,1 周前.

最后提交: 4 月,1 周前.

来源: 2018 Shanghai Metropolitan Contest

标签