// LUOGU_RID: 98998132
#include<bits/stdc++.h>
using namespace std;
inline void solve() {
	string str;
	char ch=0;
	map <char,int> cnt;
	cin>>str;
	sort(str.begin(),str.end());
	int n=str.length();
	for(int i=0;i<n;++i) ++cnt[str[i]];
	for(auto x:cnt) {
		int tot=x.second;
		if(tot==n) {
			cout<<str<<endl;
			return ;
		}
		if(tot==1&&ch==0) ch=x.first;
	}
	string ret;
	if(ch!=0) {
		ret.push_back(ch);
		for(int i=0;i<n;++i) if(str[i]!=ch) ret.push_back(str[i]);
	} else if(cnt[str.front()]<=(n/2)+1) {
		ch=str.front();
		ret.push_back(ch),ret.push_back(ch);
		cnt[ch]-=2;
		for(int i=0;i<n;++i) {
			if(str[i]!=ch) {
				ret.push_back(str[i]);
				if(cnt[ch]>0) {
					ret.push_back(ch);
					--cnt[ch];
				}
			}
		}
	} else if(cnt.size()==2) {
		for(auto &x:cnt) {
			ret.push_back(x.first);
			--x.second;
			if(ret.length()==2) break;
		}
		for(int i=1;i<=cnt[ret[1]];++i) ret.push_back(ret[1]);
		for(int i=1;i<=cnt[ret[0]];++i) ret.push_back(ret[0]);
	} else {
		for(auto &x:cnt) {
			ret.push_back(x.first);
			--x.second;
			if(ret.length()==3) {
				ch=x.first;
				break;
			}
		}
		char ch=str.front();
		while(cnt[ch]--) ret.push_back(ch);
		swap(ret[2],ret[ret.length()-1]);
		for(auto x:cnt) {
			if(x.first==ch) continue;
			for(int i=1;i<=x.second;++i) {
				ret.push_back(x.first);
			}
		}
	}
	cout<<ret<<endl;
}
signed main() {
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}