Problem Statement

For a string $s$ consisting of lowercase English letters, let $f(s)$ denote the number of substrings of $s$ that are palindromes of even length. More precisely, $f(s)$ is the number of pairs of integers $l, r$ that satisfy all of the following conditions:

• $1 \leq l \leq r \leq |s|$.
• $r - l + 1$ is even.
• $s_l s_{l+1} \cdots s_{r}$ is a palindrome.

Given a string $S$ consisting of lowercase English letters, output one string $S'$ obtained by rearranging the characters of $S$ such that $f(S')$ is minimized.

You are given $T$ test cases. Solve each of them.

Constraints

• $1 \le T \le 10^5$
• $2 \le |S| \le 2 \times 10^5$
• $S$ consists of lowercase English letters.
• The sum of $|S|$ over all test cases is at most $2 \times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

S

Output

Output $T$ lines.

The $i$-th line should contain one string $S'$ obtained by rearranging the characters of $S$ in the $i$-th test case such that $f(S')$ is minimized. If there are multiple such $S'$, any of them will be considered correct.