Longest Palindromic Substring Length

Given a string s, your task is to find the length of the longest palindromic substring in s. A substring is a contiguous sequence of characters within the string. A palindrome is a string that reads the same forwards and backwards.

The solution should use an algorithm that runs efficiently. One approach is to use dynamic programming where a table dp[i][j] is maintained to indicate whether the substring \( s_i s_{i+1} \ldots s_j \) is a palindrome.

Example:

• For s = "babad", the longest palindromic substring is "bab" (or "aba"), so the answer is 3.
• For s = "cbbd", the longest palindromic substring is "bb", so the answer is 2.

inputFormat

The first line of input contains an integer T (\(1 \le T \le 100\)) representing the number of test cases. Each of the next T lines contains a single string s.

The string s consists of lowercase English letters. Its length is between 0 and 1000, inclusive.

outputFormat

For each test case, output the length of the longest palindromic substring found in the given string. Each answer should be printed on a new line.

## sample

1
babad

3

</p>