Minimal Removal to Form Palindrome

Given a string ( s ), remove the minimum number of characters such that the resulting string is a palindrome. In other words, find a palindromic subsequence of ( s ) with maximum possible length, and output that subsequence. Note that a subsequence is obtained by deleting zero or more characters (not necessarily contiguous) from ( s ).

The problem can be formulated using dynamic programming. Let ( dp[i][j] ) denote the length of the longest palindromic subsequence in ( s[i \ldots j] ). The recurrence is given by: [ dp[i][j] = \begin{cases} 1 & \text{if } i = j, \ 2 & \text{if } s[i] = s[j] \text{ and } j = i+1, \ dp[i+1][j-1] + 2 & \text{if } s[i] = s[j], \ \max(dp[i+1][j], dp[i][j-1]) & \text{if } s[i] \neq s[j]. \end{cases} ]

Using the above recurrence, one can reconstruct the palindromic string by a greedy approach. Your task is to implement this algorithm such that the program reads input from stdin and writes output to stdout as described below.

inputFormat

The first line of input contains a single integer \( T \) indicating the number of test cases. Each of the next \( T \) lines contains a non-empty string \( s \) consisting of lowercase letters.

You should read the input from standard input (stdin).

outputFormat

For each test case, output a single line containing the palindromic string obtained by removing the minimum number of characters from \( s \). If there are multiple answers, any one is acceptable as long as it is a longest palindromic subsequence.

The output should be written to standard output (stdout).

## sample

3
abc
abac
a

a
aba
a

</p>