Description

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!)

Input Format

The first line contains an integer $n$.

Then follow $n$ lines, each containing one piece of gibberish.

Output Format

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).

1
aaaaa

5

Hint

Constraints and Conventions

For all testdata, $1\le n\le 10$, $1\le |s_i|\le 10^7$.

Translated by ChatGPT 5