Longest Palindromic Substring Problem Statement

You are provided with a string STR of length N. The task is to find the longest palindromic substring within STR. If there are several palindromic substrings of the maximum length, return the one that starts with the smallest index.

Input:

The first line of the input contains a single integer T, the number of test cases.
Each of the following T lines contains a single string STR.

Output:

For each test case, output the longest palindromic substring. If multiple substrings qualify, return the one that appears first.

Example:

Input:
2
ababc
cbbd

Output:

aba
bb

Explanation:

For first test case, "aba" and "bab" are both palindromes. "aba" is chosen because it starts earlier.

Constraints:

• 1 ≤ T ≤ 5
• 0 ≤ N ≤ 100

Note:

A substring is defined as a contiguous segment of a string.