You are given a string S, consisting of lowercase English letters. You can do the following operation at most once :

Choose a subsequence of the string S, then remove it from S and concatenate the subsequence at the end of the remaining string. 

Find the lexicographically minimum string that can be obtained by performing this operation at most once on S.

Note that:

A string A is a subsequence of a string B if A can be obtained by deleting several (possibly, zero or all) characters from B.
Given two strings of the same length A and B, we say that A is lexicographically smaller than B if there exists an index i such that A_{1}=B_{1},A_{2}=B_{2},\ldots,A_{i-1}=B_{i-1} and  A_{i}< B_{i}.

------ Input Format ------ 

- The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a string S.

------ Output Format ------ 

For each test case, print a single line containing the lexicographically minimum string which can be obtained from S by performing the given operation at most once.

------ Constraints ------ 

$1 ≤ T ≤ 2 \cdot 10^{5}$
$1 ≤\lvert S \rvert ≤10^{5}$
$S$ contains only lowercase English letters.
- Sum of $ \lvert S \rvert $ over all test cases does not exceed $10^{6}$.

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
4
aba
abcd
cbcdbef
fabcdac
----- Sample Output 1 ------ 
aab
abcd
bbccdef
aacfbcd

----- explanation 1 ------ 
Test case $1$: It is optimal to choose the subsequence $b$, then remove and concatenate the subsequence at the end of the remaining string $aa$. Hence the final string is $aa + b = aab$.

Test case $2$: The given string is already lexicographically minimum.

Test case $3$: It is optimal to choose the subsequence $ccdef$, then remove and concatenate the subsequence at the end of the remaining string $bb$. Hence the final string is $bb + ccdef = bbccdef$.

Difficulty: VERY_HARD
Tags: Constructive algorithms

String algorithms

Sorting

Combinatorics

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
def solve(s):
	len_s = len(s)
	cur = [False] * len_s
	let = 'z'
	if len_s - 1 > 0:
		for i in range(len_s - 1, 0, -1):
			if s[i] <= let:
				cur[i] = True
				let = s[i]
		if s[0] <= let:
			cur[0] = True
			let = s[0]
	before = ''
	after = ''
	got = []
	for i in range(0, len_s):
		if cur[i]:
			before += s[i]
			got.append(i)
		else:
			after += s[i]
	for i in range(len(before)):
		if len(after) > 0 and after[0] < before[i]:
			for j in range(i, len(got)):
				cur[got[j]] = False
	before = ''
	after = ''
	got = []
	for i in range(0, len_s):
		if cur[i]:
			before += s[i]
			got.append(i)
		else:
			after += s[i]
	count = 0
	for i in range(0, len(after)):
		if after[i] != after[0]:
			if after[i] > after[0]:
				break
			while len(before) > 0 and before[-1] == after[0]:
				cur[got[-1]] = False
				got.pop(-1)
				before = before[:-1]
	before = ''
	after = ''
	got = []
	for i in range(0, len_s):
		if cur[i]:
			before += s[i]
			got.append(i)
		else:
			after += s[i]
	res = before + after
	return res
t = int(input())
for i in range(t):
	s = input()
	print(solve(s))


for _ in range(int(input())):
	s = input()
	freq = [0 for i in range(26)]
	for i in s:
		freq[ord(i) - 97] += 1
	prefix = ''
	suffix = ''
	left = s
	ans = s
	for i in range(26):
		if len(left) == 0:
			break
		if freq[i] == 0:
			continue
		sc = chr(i + 97)
		ind = 0
		while freq[i] != 0 and ind < len(left):
			if left[ind] == sc:
				freq[i] -= 1
				prefix += left[ind]
			else:
				suffix += left[ind]
				freq[ord(left[ind]) - 97] -= 1
			ind += 1
		left = left[ind:]
		ans = min(ans, min(prefix + suffix + left, prefix + left + suffix))
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	if s == sorted(s):
		print(s)
		continue
	freq = [0] * 26
	for i in s:
		freq[ord(i) - ord('a')] += 1
	(pre, sub, suff, ans, index) = ('', '', s, s, 0)
	while index < 26:
		if freq[index] == 0:
			index += 1
			continue
		i = 0
		while i < len(suff) and freq[index] > 0:
			if ord(suff[i]) - ord('a') == index:
				pre += suff[i]
			else:
				sub += suff[i]
			freq[ord(suff[i]) - ord('a')] -= 1
			i += 1
		suff = suff[i:]
		ans = min(ans, pre + sub + suff)
	print(ans)


import sys
input = sys.stdin.readline
big_char = chr(ord('z') + 1)
num_test_cases = int(input())
for _ in range(num_test_cases):
	string = input().strip()
	smallest_to_the_right = [big_char]
	for letter in string[:0:-1]:
		smallest_to_the_right += [min(smallest_to_the_right[-1], letter)]
	smallest_to_the_right.reverse()
	arr = []
	subsequence = []
	second_unique_letter_in_subsequence = None
	for (letter, sufix_min) in zip(string, smallest_to_the_right):
		if sufix_min < letter or (len(subsequence) and letter > subsequence[0]) or (len(subsequence) and second_unique_letter_in_subsequence == None and (letter == subsequence[0])) or (second_unique_letter_in_subsequence != None and letter == subsequence[0] and (letter > second_unique_letter_in_subsequence)):
			subsequence += [letter]
			if second_unique_letter_in_subsequence == None and letter != subsequence[0]:
				second_unique_letter_in_subsequence = letter
		else:
			arr += [letter]
	ans = ''.join(arr + subsequence)
	print(ans)


def solve(s, n):
	if s == sorted(s):
		print(s)
		return
	freq = [0] * 26
	for i in s:
		freq[ord(i) - ord('a')] += 1
	(prefix, subseq, suffix, ans, idx) = ('', '', s, s, 0)
	while idx < 26:
		if freq[idx] == 0:
			idx += 1
			continue
		i = 0
		while i < len(suffix) and freq[idx] > 0:
			if ord(suffix[i]) - ord('a') == idx:
				prefix += suffix[i]
			else:
				subseq += suffix[i]
			freq[ord(suffix[i]) - ord('a')] -= 1
			i += 1
		suffix = suffix[i:]
		ans = min(ans, prefix + subseq + suffix)
	print(ans)
t = int(input())
for _ in range(t):
	s = input()
	solve(s, len(s))


def solve(s):
	n = len(s)
	keep = [False] * n
	sml = 'z'
	for i in range(n - 1, -1, -1):
		if s[i] <= sml:
			keep[i] = True
			sml = s[i]
	bef = aft = ''
	took = []
	for i in range(0, n):
		if keep[i]:
			bef += s[i]
			took.append(i)
		else:
			aft += s[i]
	for i in range(len(bef)):
		if len(aft) > 0 and aft[0] < bef[i]:
			for j in range(i, len(took)):
				keep[took[j]] = False
	bef = aft = ''
	took = []
	for i in range(0, n):
		if keep[i]:
			bef += s[i]
			took.append(i)
		else:
			aft += s[i]
	for i in range(0, len(aft)):
		if aft[i] != aft[0]:
			if aft[i] > aft[0]:
				break
			while len(bef) > 0 and bef[-1] == aft[0]:
				keep[took[-1]] = False
				took.pop(-1)
				bef = bef[:-1]
	bef = aft = ''
	took = []
	for i in range(0, n):
		if keep[i]:
			bef += s[i]
			took.append(i)
		else:
			aft += s[i]
	return bef + aft
t = int(input())
for i in range(t):
	s = input()
	print(solve(s))


t = int(input())
for z in range(t):
	string = str(input())
	n = len(string)
	e = min(string)
	dict = {}
	for i in string:
		if i not in dict.keys():
			dict[i] = 1
		else:
			dict[i] += 1
	sort_str = sorted(set(string))
	e = sort_str[0]
	st = ''
	end = ''
	flag = True
	for i in range(n):
		if string[i] == e and flag:
			st += string[i]
			if dict[string[i]] == 1:
				sort_str.remove(string[i])
			else:
				dict[string[i]] -= 1
			if i != n - 1:
				e = sort_str[0]
			if len(end) and e > end[0]:
				flag = False
			elif len(end) > 1 and e == end[0]:
				temp1 = end + e
				temp2 = e + end
				if temp1 < temp2:
					flag = False
		else:
			end += string[i]
			if dict[string[i]] == 1:
				sort_str.remove(string[i])
			else:
				dict[string[i]] -= 1
	print(st + end)


def c0(s):
	x = 'a'
	c = ''
	while x != 'z':
		if x in s:
			t = s.find(x)
			if len(s) == 1:
				break
			elif t == 0:
				s = s[1:]
			else:
				c = s[0]
				break
		else:
			x = chr(ord(x) + 1)
	return c

def f(s, k):
	x = 'a'
	c = ''
	m = ''
	while x != k:
		if x in s:
			m = m + x
			t = s.find(x)
			if len(s) == 1:
				s = ''
				break
			elif t == 0:
				s = s[1:]
			else:
				w = s[:t]
				c = c + w
				if t != len(s) - 1:
					s = s[t + 1:]
				else:
					s = ''
					break
		else:
			x = chr(ord(x) + 1)
	return (m, c, s)
T = int(input())
for tc in range(T):
	os = input()
	s = os[:]
	n = len(os)
	h = c0(s)
	if n == 1 or h == '':
		print(s)
	else:
		(m, c, s) = f(s, h)
		if s == '':
			print(m + c)
		else:
			p = -1
			for i in c:
				if i != h:
					if i < h:
						p = 0
					break
			if p == 0:
				print(m + c + s)
			else:
				while True:
					if h in s:
						m = m + h
						t = s.find(h)
						if len(s) == 1:
							s = ''
							break
						elif t == 0:
							s = s[1:]
						else:
							w = s[:t]
							c = c + w
							if t != len(s) - 1:
								s = s[t + 1:]
							else:
								s = ''
								break
					else:
						break
				print(m + c + s)


def solve(S, N):
	if S == sorted(S):
		print(S)
		return
	frequency = [0] * 26
	for i in S:
		frequency[ord(i) - ord('a')] += 1
	(prefix, subseq, suffix, ans, index) = ('', '', S, S, 0)
	while index < 26:
		if frequency[index] == 0:
			index += 1
			continue
		i = 0
		while i < len(suffix) and frequency[index] > 0:
			if ord(suffix[i]) - ord('a') == index:
				prefix += suffix[i]
			else:
				subseq += suffix[i]
			frequency[ord(suffix[i]) - ord('a')] -= 1
			i += 1
		suffix = suffix[i:]
		ans = min(ans, prefix + subseq + suffix)
	print(ans)
T = int(input())
for i in range(T):
	S = input()
	solve(S, len(S))


def get_sorter(line):
	if len(line) == 0:
		return ''
	for i in alphabet:
		if i in line:
			return i

def get_result(sorter, line):
	if len(line) <= 1:
		return line
	counter = 1
	remainder = ''
	for i in range(len(line) - 1, -1, -1):
		if line[i] == sorter:
			end = line[i + 1:] if i + 1 < len(line) else ''
			last_index = i
			break
	for i in range(last_index):
		if line[i] == sorter:
			counter += 1
		else:
			remainder += line[i]
	if end != '' and len(end) > 1:
		sorter2 = get_sorter(end)
		j = last_index + 1
		head = sorter * counter
		while remainder == '' or sorter2 + remainder <= remainder + sorter2:
			if j == len(line):
				return head + remainder
			if line[j] != sorter2:
				remainder += line[j]
			else:
				head += sorter2
				end = line[j + 1:]
				sorter2 = get_sorter(end)
			j += 1
		return head + remainder + end
	elif len(end) == 1:
		if end + remainder >= remainder + end:
			return sorter * counter + remainder + end
		return sorter * counter + end + remainder
	return sorter * counter + remainder
alphabet = 'abcdefghijklmnopqrstuvwxyz'
for _ in range(int(input())):
	a = input()
	print(get_result(get_sorter(a), a))


def check(s, c):
	for i in range(len(s)):
		if s[i] > c:
			return True
		elif s[i] < c:
			return False
	return True

def next1(l):
	for i in range(27):
		if l[i] > 0:
			return i
	return 0
t = int(input())
for _ in range(t):
	s = input()
	min_i = 100
	alpha = [0 for i in range(27)]
	for i in range(len(s)):
		alpha[ord(s[i]) - 96] += 1
		if ord(s[i]) - 96 < min_i:
			min_i = ord(s[i]) - 96
	ans1 = []
	ans2 = []
	for i in range(len(s)):
		if alpha[min_i] <= 0:
			min_i = next1(alpha)
		if alpha[min_i] > 0:
			if s[i] == str(chr(min_i + 96)) and check(ans2, s[i]):
				ans1.append(s[i])
			elif alpha[ord(s[i]) - 96] > 0:
				ans2.append(s[i])
			alpha[ord(s[i]) - 96] -= 1
	ans1.extend(ans2)
	print(''.join(ans1))


for _ in range(int(input())):
	S = '#' + input()
	N = len(S)
	A = ['' for _ in range(N)]
	A[N - 1] = ('.', N)
	cur = S[N - 1]
	idx = N - 1
	for i in range(N - 2, -1, -1):
		A[i] = (cur, idx)
		if S[i] <= cur:
			cur = S[i]
			idx = i
	(cur, i) = A[0]
	prefix = cur
	take = S[1:i]
	sth = S[1:]
	while True:
		prv = i
		(nxt, i) = A[i]
		if i == N:
			break
		if nxt == cur:
			prefix += nxt
			take += S[prv + 1:i]
		elif len(take) == 0:
			cur = nxt
			prefix += nxt
			take += S[prv + 1:i]
		elif take[0] < nxt:
			take += S[prv + 1:]
			break
		elif take[0] > nxt:
			cur = nxt
			prefix += nxt
			take += S[prv + 1:i]
		else:
			sth = min(sth, prefix + take + S[prv + 1:])
			cur = nxt
			prefix += nxt
			take += S[prv + 1:i]
	print(min(prefix + take, sth))


import sys, os, io
input = sys.stdin.readline
PI = 3.141592653589793
INF = float('inf')
MOD = 1000000007

def bin32(num):
	return '{0:032b}'.format(num)

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
for t in range(ii()):
	t += 1
	a = list(input().strip())
	n = len(a)
	ml = ['z' for i in range(n)]
	ml[-1] = a[-1]
	for i in range(n - 2, -1, -1):
		ml[i] = min(a[i], ml[i + 1])
	store = []
	INF = chr(ord('z') + 5)
	first = '0'
	second = '0'
	x = ''
	y = ''
	for i in range(n):
		if a[i] != ml[i]:
			y += a[i]
			if first == '0':
				first = a[i]
			elif second == '0' and first != a[i]:
				second = a[i]
		elif first == '0':
			x += a[i]
		elif first < a[i]:
			y += a[i]
			if second == '0' and first != a[i]:
				second = a[i]
		elif first > a[i]:
			x += a[i]
		elif second == '0':
			y += a[i]
		elif second < a[i]:
			y += a[i]
		else:
			x += a[i]
	print(x + y)


from typing import DefaultDict
from math import sqrt
from collections import OrderedDict
import math

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l
for _ in range(int(input())):
	bool = True
	flag = True
	ans = 1
	mod = 10 ** 9 + 7
	d = {}
	s = input()
	res = ''.join(sorted(set(s)))
	for i in range(len(s)):
		d[s[i]] = i
	dict = OrderedDict(sorted(d.items()))
	new = {}
	alpha = ''
	grt = dict[res[0]]
	for ele in dict:
		if dict[ele] >= grt:
			alpha += ele
			new[ele] = dict[ele]
			grt = dict[ele]
	fis = ''
	temp = '{'
	end = new[alpha[-1]]
	j = 0
	for i in range(len(s)):
		if i > end:
			temp += s[i]
		else:
			if i == new[alpha[j]]:
				if s[i] <= temp[0]:
					fis += s[i]
				else:
					temp += s[i]
				j += 1
			elif s[i] == alpha[j] and s[i] <= temp[0]:
				fis += s[i]
			else:
				temp += s[i]
			if len(temp) >= 2 and bool:
				temp = temp[1:]
				bool = not bool
	j = 0
	fis2 = ''
	temp2 = '{'
	end = new[alpha[-1]]
	for i in range(len(s)):
		if i > end:
			temp2 += s[i]
		else:
			if i == new[alpha[j]]:
				if s[i] < temp[0]:
					fis2 += s[i]
				else:
					temp2 += s[i]
				j += 1
			elif s[i] == alpha[j] and s[i] < temp2[0]:
				fis2 += s[i]
			else:
				temp2 += s[i]
			if len(temp2) >= 2 and flag:
				temp2 = temp2[1:]
				flag = not flag
	if temp == '{':
		temp = ''
	if temp2 == '{':
		temp2 = ''
	print(min(fis + temp, fis2 + temp2))


for _ in range(int(input())):
	s = input()
	n = len(s)
	stack = []
	temp = [-1] * n
	not_used = ''
	for i in range(n - 1, -1, -1):
		if not len(stack):
			stack.append(i)
			temp[i] = 1
		elif s[i] <= s[stack[-1]]:
			stack.append(i)
			temp[i] = 1
		else:
			not_used = s[i] + not_used
	decreasing = 0
	for i in range(1, len(not_used)):
		if not_used[i] > not_used[0]:
			break
		elif not_used[i] < not_used[0]:
			decreasing = 1
	final = [-1] * n
	ans = ''
	for ele in stack[::-1]:
		if not_used:
			if s[ele] > not_used[0]:
				break
			elif s[ele] < not_used[0]:
				ans += s[ele]
				final[ele] = 1
			elif decreasing:
				break
			else:
				ans += s[ele]
				final[ele] = 1
		else:
			break
	for i in range(n):
		if final[i] == -1:
			ans += s[i]
	print(ans)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
sys.setrecursionlimit(3 * 10 ** 5)
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
x = 0
pref = []
lvl = []
gp = []
ans = []
f = 0
w = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def dfs(i, prod, rem, n):
	if rem == 0:
		while i < len(n):
			prod *= int(n[i])
			i += 1
		return prod
	if i == len(n):
		return prod
	mx = 0
	for j in range(9 - int(n[i])):
		mx = max(dfs(i + 1, (int(n[i]) + min(j, rem)) * prod, rem - min(j, rem), n), mx)
	return mx

def hnbhai(tc):
	s = sa()
	n = len(s)
	mn = [float('inf') for i in range(len(s) + 2)]
	for i in range(len(s) - 1, -1, -1):
		mn[i] = min(mn[i + 1], ord(s[i]))
	ans = []
	second = []
	f = float('inf')
	last = 0
	idx = 0
	for i in range(n):
		if min(f, mn[i + 1]) < ord(s[i]):
			second.append(s[i])
			if f == float('inf'):
				f = ord(s[i])
			if idx == 0:
				if f < ord(s[i]):
					idx = 1
					last = 0
				if f > ord(s[i]):
					idx = 1
					last = 1
		elif f == ord(s[i]) and last:
			second.append(s[i])
		else:
			ans.append(s[i])
	print(''.join(ans) + ''.join(second))
for _ in range(sb()):
	hnbhai(_ + 1)


import secrets
import string
t = int(input())
for k in range(t):
	s = input()
	arr = []
	for i in range(len(s)):
		arr.append([s[i], i])
	arr1 = arr[:]
	arr1.sort(key=lambda x: x[0])
	dp = [False for i in range(len(s))]
	dp1 = [False for i in range(len(s))]
	start = None
	result = ''
	result1 = ''
	result += arr1[0][0]
	result1 += arr1[0][0]
	dp[arr1[0][1]] = True
	dp1[arr1[0][1]] = True
	prev = arr1[0][1]
	prev1 = arr1[0][1]
	if arr1[0][1] != 0:
		start = s[0]
	else:
		for i in range(1, len(s)):
			if arr1[i - 1][1] + 1 != arr1[i][1]:
				start = s[arr1[i - 1][1] + 1]
				break
	if start != None:
		for i in range(1, len(s)):
			if arr1[i][1] > prev and start > arr1[i][0]:
				prev = arr1[i][1]
				result += arr1[i][0]
				dp[arr1[i][1]] = True
			if arr1[i][1] > prev1 and start >= arr1[i][0]:
				prev1 = arr1[i][1]
				result1 += arr1[i][0]
				dp1[arr1[i][1]] = True
	for i in range(len(s)):
		if dp[i] == False:
			result += s[i]
		if dp1[i] == False:
			result1 += s[i]
	if result < result1:
		print(result)
	else:
		print(result1)


from sys import stdin
input = stdin.readline

def answer():
	count = [0] * 26
	for i in range(n):
		count[ord(a[i]) - 97] += 1
	ans = ''
	(front, back, start) = ('', '', 0)
	for i in range(26):
		if count[i] == 0:
			continue
		ch = chr(97 + i)
		for j in range(start, n):
			if a[j] == ch:
				if ans != '':
					ans = min(ans, front + back + a[j:n])
				else:
					ans = front + back + a[j:n]
				front += ch
				count[i] -= 1
				if count[i] == 0:
					start = j + 1
					break
			else:
				back += a[j]
				count[ord(a[j]) - 97] -= 1
	if ans != '':
		ans = min(ans, front + back)
	else:
		ans = front + back
	return ans
for T in range(int(input())):
	a = input().strip()
	n = len(a)
	print(answer())


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)

def next(s):
	return chr(ord(s) + 1)
for _ in range(int(input())):
	l = list(input())
	n = len(l)
	l1 = list(l)
	l1.sort()
	if l1 == l:
		for i in l:
			print(i, end='')
		print()
		continue
	start = min(l)
	searched = ''
	d = {}
	for i in 'abcdefghijklmnopqrstuvwxyz':
		d[i] = -1
	for i in range(n - 1, -1, -1):
		if l[i] not in searched:
			searched += l[i]
			d[l[i]] = i
	main = ''
	rest = ''
	for i in range(n):
		if l[i] == start:
			main += l[i]
			if d[l[i]] == i and i != n - 1:
				while d[start] <= i and (rest == '' or (rest != '' and start < rest[0])) and (start < 'z'):
					start = next(start)
		else:
			rest += l[i]
	ans1 = main + rest
	start = min(l)
	searched = ''
	d = {}
	for i in 'abcdefghijklmnopqrstuvwxyz':
		d[i] = -1
	for i in range(n - 1, -1, -1):
		if l[i] not in searched:
			searched += l[i]
			d[l[i]] = i
	main = ''
	rest = ''
	for i in range(n):
		if l[i] == start:
			main += l[i]
			if d[l[i]] == i and i != n - 1:
				while d[start] <= i and (rest == '' or (rest != '' and next(start) < rest[0])) and (start < 'z'):
					start = next(start)
		else:
			rest += l[i]
	ans2 = main + rest
	print(min(ans1, ans2))