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