Longest Palindromic Substring Length

You are given an integer $n$ followed by $n$ strings. Each string represents a notorious jumble of characters. Your task is to determine the length of the most beautiful contiguous subsequence for each string.

In the eyes of a true master, only palindromic subsequences are considered beautiful. A palindrome is a sequence of characters that reads the same backward as forward. Formally, a string s is a palindrome if and only if $$ s[i]=s[|s|-i-1] \quad \text{for all } 0 \leq i < |s|, $$ where $|s|$ denotes the length of the string.

For every input string, find the length of its longest palindromic substring.

Note: A substring is a contiguous sequence of characters within the string.

inputFormat

The first line contains a single integer $n$, the number of strings. Each of the following $n$ lines contains one string consisting of characters.

outputFormat

Output $n$ lines, each line containing a single integer representing the length of the longest palindromic substring of the corresponding input string.

sample

3
babad
cbbd
a

3
2
1