P1723 The Expert Celebrates April Fools' Day

The expert is organizing everyone to celebrate April Fools' Day, and the party needs some banners. Wanting to be a bit artistic, he uses some gibberish that ordinary people cannot understand as the banner content. But at the same time, he also wants the banners to look more aesthetic.

Now, you are given $n$ well-known pieces of messy gibberish. The expert wants to know the length of the most aesthetic contiguous subsequence of each piece. In the expert’s view, only palindromes are aesthetic. This represents his pure love and the beauty of cycles. Most importantly, for the expert who has “gone back to grade one,” this is too hard to compute, so he turns to you for help. (An OIer can do anything!)

The first line contains an integer $n$. Then follow $n$ lines, each containing one piece of gibberish.

Output $n$ lines. For each piece of gibberish, output the length of its most aesthetic substring, that is, the length of the longest palindromic substring (but since the expert does not understand, we will not call it that).

### Constraints and Conventions For all testdata, $1\le n\le 10$, $1\le |s_i|\le 10^7$. Translated by ChatGPT 5