B. Farouk and Password
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Farouk's course registration opens tonight at midnight, but he's having some trouble logging into banner. Not knowing what a password manager is, Farouk still creates his own passwords and writes them down in his notebook. He generates his passwords in an interesting way. He starts with a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters. Then, he is only allowed to make the following operation:

  • Select two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) such that $$$i \oplus j \lt \min(i, j)$$$$$$^{\text{∗}}$$$ and swap the letters at those indices.
He then picked his password to be the lexicographically smallest string that can be reached after performing the operation on the string $$$s$$$ any number of times. However, to be extra secure, he only wrote down the original string and can't remember the final password. Help Farouk remember his password so he can register for his courses on time.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
  • in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

$$$^{\text{∗}}$$$$$$\oplus$$$ denotes the bitwise XOR operation.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) – the number of test cases.

The only line of each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) consisting of lowercase English letters, where $$$|s|$$$ denotes the length of the string.

It is guaranteed that the the sum of $$$|s|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case output a single string – the lexicographically minimum string that can be reached from the starting string.

Example
Input
4
dog
abcdefgh
goodpassword
onetwothreefour
Output
dgo
abcdefgh
gooadpsdorsw
oenottweefhorru
Note

In the first test case, o and g can be swapped since $$$2 \oplus 3 = 1 \lt 2 = \min(2, 3)$$$ to get "dgo" which is the lexicographically smallest arrangement ($$$d \le g \le o$$$).

In the second test case, no operations were performed since it is already lexicographically smallest.