Thinking-Bear gave a necklace to the sister who he admired in the heart. The necklace is made of the lowercase letter head-tail string.
Sister looked at the necklace and said to Thinking-Bear: "I hope it is symmetrical". Thinking-Bear decided to cut a continuous part from the original necklace, 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.

The first line of the input is $T\ (1≤ T ≤ 100)$, which stands for the number of test cases you need to solve.

Each test case contains a string $S$, indicates the necklace. $(2 < |S| ≤ 100000)$.

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

7

or the sample, he can replace one letter to abcbaaa.