Longest Palindromic Substring

Given a string s, your task is to find the longest palindromic substring in s. A palindrome is a string that reads the same backward as forward. In case there are multiple answers, you may output any one of them.

The classic approach is to expand around each character (and between characters for even-length palindromes) and update the longest palindrome found.

The time complexity of the optimal solution is \(O(n^2)\), where \(n\) is the length of the string.

inputFormat

The input is read from stdin and it consists of multiple test cases. The first line contains an integer T (1 ≤ T ≤ 100), denoting the number of test cases. Each of the following T lines contains a non-empty string s whose length does not exceed 1000.

outputFormat

For each test case, print to stdout a single line containing the longest palindromic substring found in the given string. If there are multiple correct answers, output any one.

## sample

1
babad

bab

</p>