Go Back

##### Help Shweta to win The Matrix (250)

Description

The Finals of the Cognition Matrix are started . Shweta being a clever girl, has solved all the questions of the finals. Hence, she requested for a bonus question.

The event head of The Matrix, Aditya Parthasarathy is very creative. He has given a string to Shweta ( all alphabets are lowercase ).

Let us call a string ( length greater than or equal to 2 ) to be “alpha-ordered” if it consists of alphabets in the standard continuous alphabetical order. For e.g. abcd, jklmno, fg.

From the given string, Shweta is supposed to find and delete all such alpha-ordered substrings.

While solving this question, if Shweta spots 2 or more than 2 such substrings at the same time, she should delete the leftmost substring first, and then look for any other substrings to be deleted.

The final answer should not consist of any alpha-ordered substring.

But as we all know, Shweta loves to get her work done from others. So she has requested you to help her to win The Matrix.

Input

The first line of the input consists of a single integer N, denoting the number of strings given by Aditya.

N lines follow :

Each of these lines consists of a single string given by Aditya.

Output

For each of the ith given string ( 1 <= i <= N ), output the final answer ( final string ), to the corresponding given string in one single line.

Constraints

1 <= N <= 100

1 <= Input string length <= 1000

( All input alphabets are lowercase )

Example

Copy Input

Input:

3

hiauvz

abcd

ababcdc

Output:

az

c

Explanation

Test Case 2 :

As the whole string is alpha-ordered, the answer is an empty string

Test Case 3 :

String after deleting “ab” -> abcdc

String after deleting “abcd” -> c

Final Answer -> c