Minimax

time limit per test: 2 seconds

memory limit per test: 512 megabytes

Articles

Prefix function of string $t=t_1t_2…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_1t_2…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,…,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≤t≤10^5)$. Description of the test cases follows.

The only line of each test case contains string $s (1≤|s|≤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≠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]$.

Tutorial

首先考虑 $f(t) = 0$， 必然是首字母为只出现了一次。

再考虑 $f(t)=1$，若前两个字母相同，则剩余首字母必须小于等于其他字母，否则前两个首字母不同。

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+1;

int cnt[30];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while(T --) {
        string s;
        cin >> s;
        int n = s.size(), k = 0;
        for(int i = 0; i <= 26; ++ i) cnt[i] = 0;
        for(int i = 0; i < n; ++ i) {
            if (++cnt[s[i]-'a'+1] == 1) k++;
        }
        if (k == 1) cout << s;
        else {
            int id = 1;
            while(id <= 26 && cnt[id] != 1) id ++;
            if (id == 27) {
                int id = 1;
                while(cnt[id] == 0) id ++;
                if (cnt[id] - 2 <= n - cnt[id]) {
                    cnt[id] -= 2;
                    cout << char('a'+id-1) << char('a'+id-1);
                    for(int i = id+1; i <= 26; ++ i) {
                        if (cnt[i] == 0) continue;
                        while(cnt[i]--) {
                            cout << char('a'+i-1);
                            if (-- cnt[id] >= 0) cout << char('a'+id-1);
                        }
                    }
                }
                else {
                    if (k == 2) {
                        cnt[id] --;
                        cout << char('a'+id-1);
                        for(int i = id+1; i <= 26; ++ i) {
                            if (cnt[i] == 0) continue;
                            while(cnt[i] --) cout << char('a'+i-1);
                        }
                        while(cnt[id]--) cout << char('a'+id-1);
                    }
                    else {
                        cnt[id] --;
                        cout << char('a'+id-1);
                        for(int i = id+1; i <= 26; ++ i) {
                            if (cnt[i]) {
                                cnt[i] --;
                                cout << char('a'+i-1);
                                while(cnt[id] --) cout << char('a'+id-1);
                                for(int j = i+1; j <= 26; ++ j) {
                                    if (cnt[j]) {
                                        cnt[j] --;
                                        cout << char('a'+j-1);
                                        break;
                                    }
                                }
                                break;
                            }
                        }
                        for(int i = 1; i <= 26; ++ i) {
                            if (cnt[i] <= 0) continue;
                            while(cnt[i] --) cout << char('a'+i-1);
                        }
                    }
                }
            }
            else {
                cout << char('a'+id-1);
                cnt[id] --;
                for(int i = 1; i <= 26; ++ i) {
                    if (cnt[i] == 0) continue;
                    while(cnt[i] --) cout << char('a'+i-1);
                }
            }
        }
        cout << "\n";
    }
    return 0;
}