DS-S95-CA1-1

Time Limit: 1 Second    Memory Limit: 4096 KB

You can find the related question in the course page.

Input

In the first line, there will be given an anonymous integer t (t<40) which is the number of test cases. In the next following t lines, for each test case there will be a string of length at most 100000.

Output

You should print one integer per line which is the answer to the corresponding test case.

Sample Input

3
iiiimmmaaannn
eeehhsssaaan
saaammass

Sample Output

man
esan
s

Submit