Longest Palindromic Substring Length

You are given a string s. Your task is to compute the length of the longest palindromic substring in s. A substring is a contiguous sequence of characters within a string. A palindrome is a sequence that reads the same backward as forward.

For a given string \(s\) of length \(n\), you are to find the maximum \(k\) (where \(1 \le k \le n\)) such that there exists an index \(i\) with the substring \(s[i...i+k-1]\) being a palindrome.

Example:

• For s = "babad", one possible longest palindromic substring is "bab" with length 3.
• For s = "cbbd", the longest palindromic substring is "bb" with length 2.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases.

Each of the following \(T\) lines contains a non-empty string s.

Input Format:

T
s1
s2
...
sT

outputFormat

For each test case, output a single line containing the length of the longest palindromic substring of the given string.

Output Format:

L1
L2
...
LT

## sample

3
babad
cbbd
a

3
2
1

</p>