A chemical is represented by a character between 'a' to 'z'. Professor Utonium has a series of chemicals in n buckets. He wants to perform an experiment with the following steps.

• Step 1: Choose any two random positions i and j such that 0 <= i <= n-1 and 0 <= j <= n - 1.
• Step 2: Swap the buckets i and j.
• Step 3 (Optional): Go to step1 (This is an optional step. The professor can skip this step.)
• Step 4: All consecutive buckets containing the same chemical are merged into a single bucket.

Let m be the number of buckets remain after the experiment.

The result of the experiment is a string obtained by writing down the chemicals in each bucket in order from 0 to m-1 inclusive.

The professor is interested in obtaining the smallest string after the experiment. If there are many such strings, find the lexicographically smallest among them.

Input

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of a string C representing the chemicals in n buckets. ith bucket contains the chemical C[i].

Output

For each test case, find the string that the professor obtains after the experiment.

constraints

1 <= t <= 100

2 <= n <= 100

'a' <= C[i] <= 'z'

Example

Input:
3
egce
zbzbaba
ba

Output:
ceg
abz
ab

Explanation of Case #1

There are 4 buckets. The buckets initially contain the chemicals in the order e, g, c, e.

One of the possible solutions is

• The professor chooses i=0 and j=2.
• The professor swaps C[0] and C[2] → c, g, e, e.
• The professor prefers to go back to step 1.
• The professor chooses i=1 and j=3.
• The professor swaps C[1] and C[3] → c, e, e, g.
• The professor chooses to skip step 3.
• The professor merges all the consecutive buckets with same chemicals. → c, e, g.

No lexicographically smallest string can be formed other than "ceg".