LNGPALN - Longest palindrome with no adjacent duplicates

We are given a string . Determine the longest palindromic substring without any adjacent duplicates.

For example: S="ABBCBBA", longest palindromic substring is "ABBCBBBA" but it contains adjacent duplicates, so the required string is "BCB".

EDIT: If there are multiple such strings then print the lexicographical  smallest string.

Input

The first line of input contains a t, the number of test cases and the following line of each test case a string S (1 <= S <= 5000)

Output

Print the required  string.

Example

Input:
1
MBBCDCBBM

Output:
BCDCB

NOTE : String will be in uppercase only


Added by:dynamicgreedy
Date:2018-06-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Longest palindromic subsequence

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.