Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Minimax

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputPrefix function of string $$$t = t_1 t_2 \ldots t_n$$$ and position $$$i$$$ in it is defined as the length $$$k$$$ of the longest proper (not equal to the whole substring) prefix of substring $$$t_1 t_2 \ldots t_i$$$ which is also a suffix of the same substring.

For example, for string $$$t = $$$ abacaba the values of the prefix function in positions $$$1, 2, \ldots, 7$$$ are equal to $$$[0, 0, 1, 0, 1, 2, 3]$$$.

Let $$$f(t)$$$ be equal to the maximum value of the prefix function of string $$$t$$$ over all its positions. For example, $$$f($$$abacaba$$$) = 3$$$.

You are given a string $$$s$$$. Reorder its characters arbitrarily to get a string $$$t$$$ (the number of occurrences of any character in strings $$$s$$$ and $$$t$$$ must be equal). The value of $$$f(t)$$$ must be minimized. Out of all options to minimize $$$f(t)$$$, choose the one where string $$$t$$$ is the lexicographically smallest.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

The only line of each test case contains string $$$s$$$ ($$$1 \le |s| \le 10^5$$$) consisting of lowercase English letters.

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

Output

For each test case print a single string $$$t$$$.

The multisets of letters in strings $$$s$$$ and $$$t$$$ must be equal. The value of $$$f(t)$$$, the maximum of prefix functions in string $$$t$$$, must be as small as possible. String $$$t$$$ must be the lexicographically smallest string out of all strings satisfying the previous conditions.

Example

Input

3 vkcup abababa zzzzzz

Output

ckpuv aababab zzzzzz

Note

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$$$.

In the first test case, $$$f(t) = 0$$$ and the values of prefix function are $$$[0, 0, 0, 0, 0]$$$ for any permutation of letters. String ckpuv is the lexicographically smallest permutation of letters of string vkcup.

In the second test case, $$$f(t) = 1$$$ and the values of prefix function are $$$[0, 1, 0, 1, 0, 1, 0]$$$.

In the third test case, $$$f(t) = 5$$$ and the values of prefix function are $$$[0, 1, 2, 3, 4, 5]$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2021 04:21:47 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|