Longest Palindromic Substring Length

Given a string s, your task is to determine the length of the longest palindromic substring contained in s. A palindrome is a sequence that reads the same forward and backward. You can solve this problem using dynamic programming or by expanding around the center of each possible substring.

For each test case, compute \(f(s)\) where \(f(s)\) is defined as the length of the longest palindromic substring in s.

The input will consist of multiple test cases. For each test case, print the correct length on a new line.

inputFormat

The first line contains an integer T denoting the number of test cases. Each of the following T lines contains a single non-empty string s.

outputFormat

For each test case, output a single line with an integer representing the length of the longest palindromic substring in the given string.

1
babad

3