You are given a string $s$, consisting of lowercase Latin letters. While there is at least one character in the string $s$ that is repeated at least twice, you perform the following operation:

• you choose the index $i$ ($1 \le i \le |s|$) such that the character at position $i$ occurs at least two times in the string $s$, and delete the character at position $i$, that is, replace $s$ with $s_1 s_2 \ldots s_{i-1} s_{i+1} s_{i+2} \ldots s_n$.

For example, if $s=$"codeforces", then you can apply the following sequence of operations:

• $i=6 \Rightarrow s=$"codefrces";
• $i=1 \Rightarrow s=$"odefrces";
• $i=7 \Rightarrow s=$"odefrcs";

Given a given string $s$, find the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.

A string $a$ of length $n$ is lexicographically less than a string $b$ of length $m$, if:

• there is an index $i$ ($1 \le i \le \min(n, m)$) such that the first $i-1$ characters of the strings $a$ and $b$ are the same, and the $i$-th character of the string $a$ is less than $i$-th character of string $b$;
• or the first $\min(n, m)$ characters in the strings $a$ and $b$ are the same and $n < m$.

For example, the string $a=$"aezakmi" is lexicographically less than the string $b=$"aezus".

The first line contains one integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow.

Each test case is characterized by a string $s$, consisting of lowercase Latin letters ($1 \le |s| \le 2 \cdot 10^5$).

It is guaranteed that the sum of the lengths of the strings in all test cases does not exceed $2 \cdot 10^5$.

For each test case, output the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.