12034 - Longest Palindrome substring   

Status  |  Limits Submit

Description

Given N strings composed of only {'A','T','C','G'}.

That is, for any char c in the string , c == 'A' or c == 'T' or c== 'C' or c== 'G'.

Find the length of longest palindromes substring in the string and output the length.

 

Palindrome: a string that is identical to its reverse, like "level" or "aba".

 

Substring: a contiguous sequence of characters within a string. For example, 'ABC' is a substring of 'ABCDEFG', 'ABC' , 'CDEF' , 'G' do also, but 'ACDE' doesn't, because it is not contiguous in the main string. 'string' is a substring of 'substring'

 

Input

There is a number N in the first line, indicates that there will be N lines follow.

For the next N lines, each of them contains a string.

 

It is guaranteed that the length of each given string will not exceed 10000.

 

Output

For each given string, print a line contains only a integer: the length of Longest palindromes substring of that string.

 

 

Sample Input  Download

Sample Output  Download

Tags




Discuss