#include<bits/stdc++.h>
using namespace std;
int t,n,fl,nc,nd,ns,tp,sa[1000009],rnk[1000009],ban[1000009],slen[1000009];
char s[1000009],C[1000009],D[1000009],T[1000009],ans[1000009];
inline int read(){
	int s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
namespace SAM{
	int tp,tot,cnt = 1,last = 1,tmp[26],hd[2000009],fa[2000009],dy[2000009],id[2000009],len[2000009],pos[2000009],suf[2000009],ch[2000009][26];
	struct st{int x,y;}eg[2000009];
	void addedge(int u,int v){eg[++ tot] = (st){v,hd[u]},hd[u] = tot;}
	void clear(){
		for (int i = 1;i <= cnt;i += 1){
			memset(ch[i],0,sizeof(ch[i]));
			fa[i] = dy[i] = id[i] = len[i] = pos[i] = suf[i] = 0;
		}
		cnt = last = 1;
	}
	void ins(int x,int y){
		int p = last,cur = ++ cnt;
		pos[cur] = y,suf[cur] = 1,len[cur] = len[last] + 1;
		while (p && !ch[p][x]) ch[p][x] = cur,p = fa[p];
		int q = ch[p][x];
		if (!q) fa[cur] = 1;
		else if (len[p] + 1 == len[q]) fa[cur] = q;
		else{
			int r = ++ cnt;
			fa[r] = fa[q],pos[r] = pos[q],len[r] = len[p] + 1;
			memcpy(ch[r],ch[q],sizeof(ch[q]));
			while (p && ch[p][x] == q) ch[p][x] = r,p = fa[p];
			fa[cur] = fa[q] = r;
		}
		last = cur;
	}
	void dfs(int u,bool fl,bool opt){
		if (suf[u]){
			if (opt){
				if (!fl) return;
				slen[++ ns] = n - pos[u] + 1;
			}
			else tp += 1,sa[tp] = pos[u],rnk[pos[u]] = tp;
		}
		for (int i = hd[u];i;i = eg[i].y) dfs(eg[i].x,fl,opt),fl = 0;
	}
	void work(int opt){
		tp = tot = 0;
		for (int i = 0;i < 26;i += 1) tmp[i] = 0;
		for (int i = 1;i <= cnt;i += 1) hd[i] = 0;
		for (int i = 1;i <= cnt;i += 1) dy[i] = T[pos[i] + len[fa[i]]] - 'a',tmp[dy[i]] += 1;
		for (int i = 1;i < 26;i += 1) tmp[i] += tmp[i - 1];
		for (int i = 1;i <= cnt;i += 1) id[tmp[dy[i]] --] = i;
		for (int i = cnt;i >= 1;i -= 1) if (fa[id[i]]) addedge(fa[id[i]],id[i]);
		dfs(1,1,opt);
	}
}
void upd(){
	for (int i = 1;i <= n;i += 1){
		if (ans[i] < T[i]) return;
		if (ans[i] > T[i]){
			for (int j = 1;j <= n;j += 1) ans[j] = T[j];
			return;
		}
	}
}
void simulate(int o){
	int nc = 0,nd = 0,pos = 1;
	for (int i = 1;i <= o;i += 1){
		if (s[i] <= s[pos]) C[++ nc] = s[i],pos = i;
		else D[++ nd] = s[i];
	}
	reverse(C + 1,C + nc + 1);
	int tp = 0,cpos = 1;
	for (int i = o + 1;i <= n;i += 1){
		while (cpos <= nc && C[cpos] < s[i]) T[++ tp] = C[cpos ++];
		T[++ tp] = s[i];
	}
	while (cpos <= nc) T[++ tp] = C[cpos ++];
	for (int i = 1;i <= nd;i += 1) T[++ tp] = D[i];
	if (!fl) for (int i = 1;i <= n;i += 1) ans[i] = T[i];
	else upd();
	fl = 1;
}
void clear(){
	SAM :: clear();
	fl = nc = nd = ns = tp = 0;
	for (int i = 1;i <= n;i += 1) sa[i] = rnk[i] = ban[i] = slen[i] = 0;
}
int main(){
	t = read();
	while (t --){
		clear(),scanf("%s",s + 1),n = strlen(s + 1);
		int pos = 1;
		for (int i = 1;i <= n;i += 1) if (s[i] <= s[pos]){
			C[++ nc] = s[i];
			for (int j = pos + 1;j < i;j += 1) D[++ nd] = s[j];
			pos = i;
		}
		reverse(C + 1,C + nc + 1);
		for (int i = 1;i <= nc;i += 1) T[i] = C[i];
		for (int i = 1;i <= nd;i += 1) T[i + nc] = D[i];
		for (int i = pos + 1;i <= n;i += 1) T[i] = s[i];
		for (int i = n;i > pos;i -= 1) SAM :: ins(T[i] - 'a',i);
		SAM :: work(1);
		for (int i = pos;i >= 1;i -= 1) SAM :: ins(T[i] - 'a',i);
		SAM :: work(0);
		for (int i = 2;i < ns;i += 1) if (slen[i] - slen[i - 1] == slen[i + 1] - slen[i]) ban[i] = 1;
		for (int i = 0;i <= ns;i += 1){
			if (i <= 1 || i == ns || !ban[i - 1] || !ban[i]) simulate(n - slen[i]);
		}
		for (int i = 1;i <= n;i += 1) putchar(ans[i]);
		puts("");
	}
	return 0;
}