Longest Palindromic Substring Length

You are given a string s. The task is to find the length of the longest substring of s which is a palindrome. A palindrome is a string that reads the same backwards as forwards. For example, given the string "babad", one possible longest palindromic substring is "bab" which has a length of 3.

More formally, if you denote a substring of s by s[i...j], you need to find the maximum L such that there exists i and j with j-i+1 = L and s[i...j] is a palindrome. In mathematical terms, for a substring s[i...j] to be a palindrome, it must satisfy:

$$s[i] = s[j], \quad s[i+1] = s[j-1], \quad \dots \quad \text{for all valid indices}. $$

Your program should be able to handle multiple test cases. For each test case, determine the length of the longest palindromic substring.

inputFormat

The input will be given via standard input (stdin) and is formatted as follows:

1. The first line contains an integer T, the number of test cases.
2. Each of the next T lines contains a single string s.

Constraints:

• 1 ≤ T ≤ 50
• 1 ≤ |s| ≤ 1000 where |s| is the length of the string.

outputFormat

For each test case, output the length of the longest palindromic substring. Each result should be printed on a new line to standard output (stdout).

## sample

2
babad
cbbd

3
2

</p>