Longest Palindromic Substring

Mary is fascinated with palindromes and loves to experiment with strings. A palindrome is a string that reads the same backward as forward. Given a string s, your task is to find its longest palindromic substring. If there are multiple answers, output the one that appears first.

The problem can be formulated as finding an index pair \( (i,j) \) such that the substring \( s[i \ldots j] \) is a palindrome and \( j-i+1 \) is maximized. For example, for the string babad, one valid answer is bab (even though aba is also a palindrome of equal length).

inputFormat

The input is given from standard input (stdin). The first line contains an integer T, representing the number of test cases. Each of the following T lines contains a non-empty string s (consisting of lowercase English letters) for which you need to determine the longest palindromic substring.

outputFormat

For each test case, output the longest palindromic substring in a separate line on standard output (stdout). If there exist multiple palindromic substrings of maximum length, output the one that appears first.

2
babad
cbbd

bab
bb