Given a string, return the longest palindromic substring (LPS) in it.

Note: There can be multiple palindromic substrings with the max length. In case of conflict, return the substring that has the smallest starting index.

Examples

str: "abcdcab"
LPS: "cdc"

str: "abcdcba"
LPS: "abcdcba"

str: "abcd"
LPS: "a"

str: "abaadcd"
LPS: "aba"

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input contains a string.

Output Format

For each test case, the output contains a line with one string denoting the LPS.

Sample Input

5
abcdcab
abcdcba
abcd
abaadcd
workattech

Expected Output

cdc
abcdcba
a
aba
tt

Constraints

1 <= T <= 100
1 <= string length <= 500
The string contains only lowercase english alphabets