Description

Hi and Ho are good friends. Because of born in the information society, they have a great interest in programming. They agreed to help each other, along the way of learning on the programming.

One day, they met a string. Hi put a question to Ho:”Ho, I find some interesting strings. I name them Hi-Ho String. can you find the Hi-Ho String in these strings?”

Ho felt strange and asked:”what is the Hi-Ho String?”

Hi replied:”We can find lots of strings. Ther are consecutive substrings of a string. And them are palindromes, meaning them read the same backward and forward. Hi-Ho String is the longest string of them.”

Ho said:”I see I see. So how do I get Hi-Ho String? How do I tell you the way I calculate it?”

Hi said with a smile:”It is so easy, you just need to write a program. At first you input a integer $N(N \leq 10^3)$, it means the number of strings I given you. Then the next is the strings I give to you( $length of string \leq 10^6$ ). And you should tell me the length of Hi-Ho String.”

Format

Input

The first line is an integer $T(1 \leq T \leq 1000)$, indicating the number of test cases.The length of string must less than $100000$.

Output

Print the max length of Hi-Ho String.

Samples

3
abababa
aaaabaa
acacdas

7
5
3