Alicia and Roberto like to play games. Today, Roberto is trying to guess a secret word that Alicia chose. Alicia wrote a long string S in a piece of paper and gave Roberto the following clues:
Roberto knows Alicia very well, and he’s sure that if there are several possible secret words that satisfy the clues above, Alicia must have chosen the longest one.
Can you help him guess the secret word?
Input
The first line of the input file contains a single integer number T ≤ 150, the number of test cases.
T lines follow, each with a single string S. S will only contain lowercase English letters. The length of S will not exceed one million characters.
Output
For each test case, output the secret word in one line.
Sample input and output
standard input
|
standard output
|
5
colombia abcdba neversayeven neveroddoreven listentothesilence |
c
ba even neveroddoreven sil |
Explanation of the sample cases
1A substring of S is defined as any consecutive sequence of characters belonging to S. For example, if S = abcd then a, abcd, ab, bc and bcd are some of the substrings of S but ac, aa, aabbccdd and dcba are not substrings of S.