OMITRED - Omitting Redundancy

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

Added by:[UNI]Jonathans
Date:2013-03-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:TJU Team Selection Contest 2009 (4)

hide comments
2023-03-15 14:21:03 Simes
Perhaps I missed something obvious, but I found it quite tricky, and worthy of a classical problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.