A. Cool Strings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an string $$$s$$$, you go from left to right and append the unique characters in order of their appearance to an empty string $$$x_1$$$ and delete that character from it's position in $$$s$$$, if there are no more unique characters to be appended to $$$x_1$$$ you will create new string $$$x_2$$$ and start appending to it and so on... In the other words you will create $$$x_1,x_2,\dots x_k$$$ strings of unique characters as long as $$$s$$$ becomes empty.

Now your task is to print the last string that is created after end of this process, which is actually $$$x_k$$$.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ — the number of test cases.

$$$$$$1 \le t \le 100$$$$$$

The first line of each test case contains an string $$$s$$$ consisting of lowercase letters.

$$$$$$1 \le |s| \le 2 \cdot 10^5$$$$$$

It is guaranteed that sum of lengths overall testcases won't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the last shortest string after this process.

Example
Input
3
aaabbc
hgghi
xyz
Output
a
gh
xyz
Note

In the first test case, $$$s = $$$"aaabbc" $$$x_1 = $$$"abc" $$$x_2 = $$$"ab" $$$x_3 = $$$"a"

For second test case, $$$s = $$$"hgghi" $$$x_1 = $$$"hgi" $$$x_2 = $$$"gh"