Longest Palindromic Substring Length

Given a string s, your task is to find the length of its longest palindromic substring. A substring is a contiguous sequence of characters within a string. A palindrome is a string that reads the same backward as forward.

The problem requires processing multiple test cases. For each test case, you are given a string, and you should output an integer representing the length of its longest palindromic substring.

The palindrome length can be computed using an algorithm such as the expand-around-center method or dynamic programming. In this problem, you need to implement an efficient solution that passes all the provided test cases.

Note: If the string is empty, the longest palindromic substring length is 0. Otherwise, even a single character is considered as a palindrome of length 1.

inputFormat

The first line of input contains a single integer T (T ≥ 1) indicating the number of test cases. Each of the next T lines contains a non-empty string s consisting of lowercase or uppercase English letters. Each test case should be read from standard input (stdin).

outputFormat

For each test case, output a single integer on a separate line denoting the length of the longest palindromic substring found in the input string. The output should be printed to standard output (stdout).## sample

2
babad
cbbd

3
2