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:
MBBCDCBBM
Output:
BCDCB

NOTE : String will be in uppercase only