Given a string which only consists of lowercase letters, your task is to remove the redundant letters so that each letter will appear exactly once in the goal string, and the goal string is a subsequence of the original string. Since there are lots of solutions, return the lexicographically smallest one.

Note:
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, ABD is a subsequence of ABCDEF.

Input

The first line of data contains an integer T (T <= 20) indicating the number of test cases.

For each test case, there is a string whose length will not exceed 100.

Output

Output the goal string with the smallest lexicographic order in one line for every case.

Example

Input:
2
diskette
tata

Output:
disket
at