Lexicographically Smallest Subsequence

Given a string s, your task is to find the lexicographically smallest subsequence of s that contains all the distinct characters in s exactly once. A subsequence is a sequence that can be derived from the string by deleting some elements without changing the order of the remaining elements. This is a classic greedy problem where you must carefully choose characters to ensure that the final sequence is as small as possible in lexicographic order.

The input begins with an integer t, denoting the number of test cases. For each test case, a single line with the string s is provided. For each test case, output the lexicographically smallest subsequence on a new line.

Note: All letters in the string are assumed to be lowercase English letters.

inputFormat

The first line of input contains an integer t (1 ≤ t ≤ 100), the number of test cases. Each of the following t lines contains a non-empty string s, consisting of lowercase English letters only, with a length of up to 10^5.

outputFormat

For each test case, output a single line containing the lexicographically smallest subsequence of s that contains every distinct character exactly once.## sample

1
abcabc

abc