You have a string $s$ consisting of digits from $0$ to $9$ inclusive. You can perform the following operation any (possibly zero) number of times:

You can choose a position $i$ and delete a digit $d$ on the $i$-th position. Then insert the digit $\min{(d + 1, 9)}$ on any position (at the beginning, at the end or in between any two adjacent digits).

What is the lexicographically smallest string you can get by performing these operations?

A string $a$ is lexicographically smaller than a string $b$ of the same length if and only if the following holds:

in the first position where $a$ and $b$ differ, the string $a$ has a smaller digit than the corresponding digit in $b$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the test cases follow.

Each test case consists of a single line that contains one string $s$ ($1 \le |s| \le 2 \cdot 10^5$) — the string consisting of digits. Please note that $s$ is just a string consisting of digits, so leading zeros are allowed.

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


-----Output-----

Print a single string — the minimum string that is possible to obtain.


-----Examples-----

Input
4
04829
9
01
314752277691991
Output
02599
9
01
111334567888999


-----Note-----

In the first test case:

Delete $8$ and insert $9$ at the end of the notation. The resulting notation is $04299$.

Delete $4$ and insert $5$ in the $3$-rd position of the notation. The resulting notation is $02599$.

Nothing needs to be done in the second and third test cases.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Data structures

Mathematics

Greedy algorithms


Solutions:
T = int(input())
for i in range(T):
	S = input()
	minn = S[-1]
	res = []
	for i in S[-2::-1]:
		if i > minn:
			if i == '9':
				res.append(i)
			else:
				res.append(str(int(i) + 1))
		else:
			res.append(minn)
			minn = i
	res.append(minn)
	res.sort()
	print(''.join(res))


def calculation(strList):
	number = [0 for x in range(10)]
	smallest = 10
	for x in range(len(strList) - 1, -1, -1):
		if strList[x] <= smallest:
			smallest = strList[x]
			number[strList[x]] += 1
		else:
			add = min(strList[x] + 1, 9)
			number[add] += 1
	result = ''
	for x in range(10):
		result += str(x) * number[x]
	return result
n = int(input())
answer = []
for x in range(n):
	s = input()
	strList = []
	for x in s:
		strList.append(x)
		strList[-1] = int(strList[-1])
	result = calculation(strList)
	answer.append(result)
for y in range(n):
	print(answer[y])


for _ in range(int(input())):
	s = input()
	mi = s[-1]
	ans = []
	for i in s[-2::-1]:
		if mi >= i:
			ans.append(mi)
			mi = i
		else:
			ans.append(str(min(int(i) + 1, 9)))
	ans.append(mi)
	ans.sort()
	print(''.join(ans))


def solve():
	s0 = list(input())
	n = len(s0)
	mini = '9'
	for i in range(n - 1, -1, -1):
		if s0[i] <= mini:
			mini = s0[i]
		else:
			s0[i] = str(min(int(s0[i]) + 1, 9))
	s0.sort()
	print(''.join(s0))
for _ in range(int(input())):
	solve()


import sys
import random
for _ in range(int(input())):
	s = input()
	min_num = s[-1]
	ans = []
	for num in reversed(s):
		if num <= min_num:
			ans.append(num)
			min_num = num
		else:
			ans.append(str(min(int(num) + 1, 9)))
	print(''.join(sorted(ans)))


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	s = input()
	n = len(s)
	net = list(s)
	mini = '9'
	for i in range(n - 1, -1, -1):
		if net[i] <= mini:
			mini = net[i]
		else:
			net[i] = str(min(int(net[i]) + 1, 9))
	ans = ''.join(sorted(net))
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
output = []
for i in range(t):
	s = input()[::-1]
	if all((d == s[0] for d in s)):
		output.append(s)
		continue
	digits = [int(x) for x in s]
	n = len(digits)
	rest = []
	while digits != []:
		m = min(digits)
		start = digits.index(m)
		for d in digits[start:]:
			if d != m:
				rest.append(min(d + 1, 9))
			else:
				rest.append(m)
		digits = digits[:start]
	rest.sort()
	output.append(''.join(map(str, rest)))
for o in output:
	print(o)


import sys

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

def N():
	return int(input())

def V():
	return map(int, input().split())

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

def C():
	return [i for i in input()]

def solve():
	for _ in range(int(input())):
		s = list(input())
		m = s[-1]
		ans = []
		for i in s[::-1]:
			if i <= m:
				ans.append(i)
				m = i
			else:
				ans.append(str(min(int(i) + 1, 9)))
		print(''.join(sorted(ans)))
solve()


for _ in range(int(input())):
	s = input()
	min_num = s[-1]
	ans = []
	for num in reversed(s):
		if num <= min_num:
			ans.append(num)
			min_num = num
		else:
			ans.append(str(min(int(num) + 1, 9)))
	print(''.join(sorted(ans)) + '\n')


for j in range(int(input())):
	str1 = input()
	minimum = str1[-1]
	output = list()
	for i in reversed(str1):
		if i <= minimum:
			output.append(i)
			minimum = i
		else:
			output.append(str(min(int(i) + 1, 9)))
	print(''.join(sorted(output)))


import sys

def main():
	t = int(sys.stdin.readline()[:-1])
	for _ in range(t):
		s = list(map(int, sys.stdin.readline()[:-1]))
		(p, r) = ([], [])
		for i in range(len(s) - 1, -1, -1):
			if len(p) == 0 or p[-1] >= s[i]:
				p.append(s[i])
			else:
				r.append(min(s[i] + 1, 9))
		r.sort(reverse=True)
		ans = []
		while p:
			if len(r) > 0:
				if p[-1] <= r[-1]:
					ans.append(str(p.pop()))
				else:
					ans.append(str(r.pop()))
			else:
				ans.append(str(p.pop()))
		while r:
			ans.append(str(r.pop()))
		print(''.join(ans))
main()


for t in range(int(input())):
	n = input()
	min_num = n[-1]
	c = []
	for i in n[::-1]:
		if i <= min_num:
			c.append(i)
			min_num = i
		else:
			c.append(str(min(int(i) + 1, 9)))
	print(''.join(sorted(c)))


n = int(input())
for i in range(n):
	a = [int(i) for i in input()]
	b = list(reversed(a))
	c = []
	c.append(b[0])
	now = b[0]
	for i in b[1:]:
		if i > now:
			if i != 9:
				c.append(i + 1)
			else:
				c.append(9)
		else:
			now = i
			c.append(i)
	c.sort()
	print(''.join((str(i) for i in c)))


for _ in range(int(input())):
	s = input()
	mn = '99999999'
	l = []
	for i in s[::-1]:
		if i <= mn:
			l.append(i)
			mn = i
		else:
			l.append(str(min(int(i) + 1, 9)))
	print(''.join(sorted(l)))


t = int(input())

def solve():
	s = input()
	lst = []
	for i in range(len(s)):
		lst += [int(s[i])]
	ch = 9
	for i in range(len(lst) - 1, -1, -1):
		if lst[i] <= ch:
			ch = lst[i]
		elif lst[i] != 9:
			lst[i] += 1
	lst.sort()
	print(''.join((str(ele) for ele in lst)))
while t:
	solve()
	t -= 1


import sys, math
input = sys.stdin.readline
INF = int(1000000000.0) + 7

def solve():
	s = list(map(int, input().rstrip()))
	n = len(s)
	cnt = [0] * 10
	for i in s:
		cnt[i] += 1
	cnt2 = [0] * 10
	idx = 0
	ans = ''
	cnt1 = [0] * 10
	for i in range(n):
		while cnt[idx] == 0:
			idx += 1
		if idx == s[i]:
			ans += str(idx)
			cnt[s[i]] -= 1
			cnt1[s[i]] += 1
		else:
			cnt[s[i]] -= 1
			cnt2[min(s[i] + 1, 9)] += 1
	real = ''
	for i in range(10):
		real += str(i) * (cnt1[i] + cnt2[i])
	print(real)
t = 1
t = int(input())
for i in range(1, t + 1):
	solve()


t = int(input())
for _ in range(t):
	l = input()
	l = [int(li) for li in l]
	minm = l[len(l) - 1]
	for i in range(len(l) - 2, -1, -1):
		if l[i] <= minm:
			minm = l[i]
		elif l[i] != 9:
			l[i] += 1
	print(''.join((str(x) for x in sorted(l))))


t = int(input())
while t > 0:
	x = input()
	a = '9'
	s = [0 for i in range(10)]
	for i in x[::-1]:
		if i <= a:
			s[ord(i) - ord('0')] += 1
			a = i
		elif i != '9':
			s[ord(i) - ord('0') + 1] += 1
		else:
			s[10 - 1] += 1
	f = []
	for i in range(10):
		d = s[i]
		while d > 0:
			f.append(str(i))
			d -= 1
	print(''.join(f))
	t -= 1


def ans(s):
	if len(s) == 1:
		return ''.join(s)
	left = len(s) - 1
	right = left
	left -= 1
	while left < right and left >= 0:
		if s[left] <= s[right]:
			right = left
			left -= 1
		else:
			e = s[left]
			s[left] = ''
			s.append(str(min(9, int(e) + 1)))
			left -= 1
	return ''.join(sorted(s))
t = int(input())
for _ in range(t):
	s = input()
	print(ans([x for x in s]))


t = int(input())
for _ in range(t):
	n = input()
	s = ''
	ar = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
	char = max(ar)
	for i in n[:][::-1]:
		if i == '9':
			s += ar[9]
		elif i <= char:
			s += ar[int(i) - int('0')]
			char = i
		else:
			s += ar[int(i) - int('0') + 1]
	s = sorted(s)
	print(''.join(s))


import bisect
for t in range(int(input())):
	s = input()
	dct = {}
	for i in range(len(s)):
		if s[i] in dct:
			dct[s[i]].append(i)
		else:
			dct[s[i]] = [i]
	s = ''.join(sorted(set(s)))
	ans = []
	res = 0
	for i in s:
		temp = dct[i]
		n = len(temp)
		ind = bisect.bisect_left(temp, res)
		l = [i] * (n - ind)
		ans += l
		if i == '9':
			l = [i] * ind
			ans += l
		else:
			l = [chr(ord(i) + 1)] * ind
			ans += l
		res = max(res, temp[-1])
	print(''.join(ans))


t = int(input())
for i in range(t):
	x = input()
	x = list(x)
	x = [int(n) for n in x]
	x.reverse()
	min = 10
	k = len(x)
	for j in range(0, k):
		if x[j] <= min:
			min = x[j]
		else:
			x[j] = x[j] + 1
			if x[j] == 10:
				x[j] = 9
	x.sort()
	ans = ''
	for k in x:
		ans += str(k)
	print(ans)


for _ in range(int(input())):
	s = input()
	l = list(s)
	l.reverse()
	m = 10
	for i in range(len(s)):
		if int(l[i]) <= m:
			m = int(l[i])
		else:
			l[i] = str(min(int(l[i]) + 1, 9))
	print(''.join(sorted(l)))


def minim(g_str):
	arr = []
	k = int(g_str[len(g_str) - 1])
	arr.append(k)
	for i in range(len(g_str) - 1, 0, -1):
		if int(g_str[i - 1]) > k:
			if int(g_str[i - 1]) == 9:
				arr.append(9)
			else:
				arr.append(int(g_str[i - 1]) + 1)
		else:
			k = int(g_str[i - 1])
			arr.append(int(g_str[i - 1]))
	arr.sort()
	return arr
k = int(input())
for i in range(k):
	g_str = input()
	print(''.join([str(x) for x in minim(g_str)]))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	nums = list(map(int, list(input().rstrip())))
	dic = dict()
	for x in range(10):
		dic[x] = []
	for num in range(len(nums)):
		dic[nums[num]].append(num)
	ma = -1
	result = []
	for x in range(10):
		for y in dic[x]:
			if ma < y:
				ma = y
				result.append(str(x))
			else:
				result.append(str(min(x + 1, 9)))
	result1 = ''
	result.sort()
	for x in result:
		result1 += x
	print(result1)


from collections import defaultdict, Counter

def solver(A, B, target):
	maxx = 0
	for (x, y) in zip(A, B):
		maxx = max(maxx, y + target - x)
	return maxx

def solve():
	s = input()
	hs = defaultdict(int)
	minn = 10
	ans = []
	for i in range(len(s) - 1, -1, -1):
		if int(s[i]) > minn:
			bpoint = i
			hs[min(int(s[i]) + 1, 9)] += 1
		else:
			hs[int(s[i])] += 1
			minn = min(minn, int(s[i]))
	ans = ans[::-1]
	for i in range(0, 11):
		if i in hs:
			ans.extend([i] * hs[i])
	print(''.join(map(str, ans)))
for _ in range(int(input())):
	solve()


t = int(input())

def solve():
	s = [int(x) for x in input()]
	n = len(s)
	not_removed = [0 for i in range(10)]
	removed = [0 for i in range(10)]
	start = 0
	for i in range(9):
		if i in s:
			for j in range(len(s)):
				if s[j] == i:
					ilast = j
			for x in s[:ilast + 1]:
				if x == i:
					not_removed[x] += 1
				else:
					removed[min(x + 1, 9)] += 1
			s = s[ilast + 1:]
	removed[9] += len(s)
	nums = [x + y for (x, y) in zip(not_removed, removed)]
	print(''.join((str(i) * x for (i, x) in enumerate(nums))))
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	s = input()
	st = []
	ans = []
	for c in s:
		while ans and ans[-1] > c:
			st.append(min(9, int(ans.pop()) + 1))
		ans.append(c)
	st = [str(i) for i in st]
	ans.extend(st)
	ans.sort()
	print(''.join(ans))


t = int(input())
while t:
	s = input()
	arr = [x for x in s]
	mn = 9
	for i in range(len(s) - 1, -1, -1):
		if int(arr[i]) <= mn:
			mn = int(arr[i])
		else:
			arr[i] = str(min(int(arr[i]) + 1, 9))
	print(''.join(sorted(arr)))
	t -= 1


for t in range(int(input())):
	s = input()
	m = s[-1]
	ans = []
	for i in reversed(s):
		m = min(i, m)
		if i <= m:
			ans.append(i)
		else:
			ans.append(str(min(int(i) + 1, 9)))
	print(''.join(sorted(ans)))


import sys

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s)

def invr():
	return map(int, input().split())

def main():
	t = inp()
	for i in range(t):
		s = insr()
		m = 9
		for i in reversed(range(len(s))):
			v = int(s[i])
			s[i] = int(s[i])
			if v < m:
				m = v
			if v > m:
				s[i] = min(9, v + 1)
		s = sorted(s)
		ss = ''
		for l in s:
			ss += str(l)
		print(ss)
main()


from collections import defaultdict
t = int(input())
for _ in range(t):
	s = input()
	res = 9
	check = defaultdict(int)
	for i in s[::-1]:
		x = int(i)
		if res >= x:
			check[min(x, 9)] += 1
			res = x
		else:
			check[min(x + 1, 9)] += 1
	for (k, v) in sorted(check.items()):
		print(str(k) * v, end='')
	print()


for _ in range(int(input())):
	s = list(input())
	s = [int(i) for i in s]
	dick = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
	for i in s:
		dick[i] += 1
		continue
	s1 = s[::-1]
	min = 9
	for i in s1:
		if i < min:
			min = i
			continue
		if i > min:
			if i == 9:
				continue
			dick[i] -= 1
			dick[i + 1] += 1
			continue
		continue
	ans = []
	for i in range(10):
		ans += [i] * dick[i]
		continue
	ans = ''.join((str(i) for i in ans))
	print(ans)
	continue


T = int(input())
for _ in range(T):
	x = input()
	x = [int(x) for x in list(x)]
	lx = len(x)
	smallest = x[-1]
	inc = []
	same = []
	for ii in range(lx - 1, -1, -1):
		if x[ii] > smallest:
			inc.append(min(x[ii] + 1, 9))
		else:
			same.append(x[ii])
			smallest = x[ii]
	res = inc + same
	res = sorted(res)
	print(''.join((str(x) for x in res)))


import sys
import math as mt
from collections import Counter

def gi():
	return list(map(int, sys.stdin.readline().strip().split()))

def gs():
	return sys.stdin.readline().strip()

def fun(a):
	ans = []
	arr = []
	for i in a:
		if not ans:
			ans.append(i)
		else:
			while ans and ans[-1] > i:
				x = int(ans.pop())
				arr.append(min(x + 1, 9))
			ans.append(i)
	ans += arr
	ans = list(map(int, ans))
	ans.sort()
	ans = list(map(str, ans))
	return ''.join(ans)
for _ in range(int(input())):
	a = input()
	print(fun(a))


t = int(input())
for test in range(t):
	s = input()
	num_s = list()
	for i in s:
		num_s.append(int(i))
	num_t = num_s[-1]
	for i in range(len(s) - 2, -1, -1):
		if num_s[i] > num_t:
			if num_s[i] < 9:
				num_s[i] += 1
		else:
			num_t = num_s[i]
	num_s.sort()
	ans = ''
	for i in num_s:
		ans += str(i)
	print(ans)


for _ in range(int(input())):
	s = input()
	m = s[-1]
	ans = []
	for elem in s[::-1]:
		m = min(m, elem)
		if elem > m:
			ans.append(min(int(elem) + 1, 9))
		else:
			ans.append(elem)
	ans = [str(num) for num in ans]
	ans.sort()
	print(''.join(ans))


for _ in range(int(input())):
	s = input()
	dit = {}
	for i in range(len(s)):
		if s[i] in dit:
			dit[s[i]].append(i)
		else:
			dit[s[i]] = [i]
	arr = sorted(dit)
	ans = ''
	m = -1
	for e in arr:
		for idx in dit[e]:
			if idx > m:
				ans += e
				m = idx
			elif e == '9':
				ans += e
			else:
				ans += str(int(e) + 1)
	print(''.join(sorted(ans)))


def solve(num):
	left = 0
	nums = []
	for i in range(len(num)):
		nums.append((int(num[i]), i))
	nums.sort()
	prev = nums[0][1]
	for i in range(1, len(nums)):
		if nums[i][1] > prev:
			prev = nums[i][1]
		else:
			nums[i] = (min(nums[i][0] + 1, 9), nums[i][0])
	res = ''
	nums.sort()
	for i in nums:
		res += str(i[0])
	return res
t = int(input())
for _ in range(t):
	n = input()
	print(solve(n))


t = int(input())
result = []
for i in range(t):
	s = input()
	n = len(s)
	FIFO = [['9', -1]]
	indiceMin = FIFO[0][1]
	Minimum = FIFO[0][0]
	for j in range(n - 1, -1, -1):
		if s[j] <= Minimum:
			Minimum = s[j]
			indiceMin = j
			FIFO.insert(0, [Minimum, indiceMin])
	if Minimum == '9':
		result.append(s)
	else:
		d = {'0': -1, '1': -1, '2': -1, '3': -1, '4': -1, '5': -1, '6': -1, '7': -1, '8': -1, '9': -1}
		for j in range(n):
			if j == indiceMin:
				del FIFO[0]
				indiceMin = FIFO[0][1]
				Minimum = FIFO[0][0]
			if (s[j] > Minimum) & (j < indiceMin) & (s[j] != '9'):
				sjPlusOne = str(int(s[j]) + 1)
				if d[sjPlusOne] == -1:
					d[sjPlusOne] = 1
				else:
					d[sjPlusOne] += 1
			elif d[s[j]] == -1:
				d[s[j]] = 1
			else:
				d[s[j]] += 1
		ch = ''
		l = [i for i in d.keys() if d[i] != -1]
		for c in l:
			ch += c * d[c]
		result.append(ch)
for i in result:
	print(i)


t = int(input())
for tt in range(t):
	orgs = []
	p1 = []
	s = list(map(int, input()))
	s.reverse()
	m = s[0]
	for i in s:
		m = min(i, m)
		if i > m:
			p1.append(min(9, i + 1))
		else:
			orgs.append(i)
	print(''.join(map(str, sorted(p1 + orgs))))


for _ in range(int(input())):
	sa = input()
	a = list((int(x) for x in sa))
	a.reverse()
	ma = 10
	for i in range(len(sa)):
		if a[i] > ma:
			a[i] = min(a[i] + 1, 9)
		ma = min(a[i], ma)
	print(''.join((str(x) for x in sorted(a))))


for _ in range(int(input())):
	s = input()
	stk = []
	res = ''
	for n in s:
		while stk and stk[-1] > n:
			res += str(min(9, int(stk.pop()) + 1))
		stk.append(n)
	while stk:
		res += stk.pop()
	print(''.join(sorted(res)))


for _ in range(int(input())):
	s = input()
	m = s[-1]
	ans = []
	for i in range(len(s) - 1, -1, -1):
		m = min(m, s[i])
		if s[i] <= m:
			ans.append(s[i])
		else:
			ans.append(str(min(int(s[i]) + 1, 9)))
	print(''.join(sorted(ans)))


t = int(input())
while t != 0:
	s = input()
	minm = 10000000000.0
	l = []
	for i in range(len(s) - 1, -1, -1):
		if int(s[i]) <= minm:
			minm = int(s[i])
			l.append(int(s[i]))
		else:
			l.append(min(int(s[i]) + 1, 9))
	l.sort()
	ans = ''.join(map(str, l))
	print(ans)
	t -= 1


t = int(input())
from bisect import bisect_left
for ncase in range(1, t + 1):
	s = [int(i) for i in input()]
	m = 9
	d = {i: [] for i in range(10)}
	for i in range(len(s)):
		d[s[i]].append(i)
		if s[i] < m:
			m = s[i]
	maxi = d[m][-1]
	ans = str(m) * len(d[m])
	for i in range(m + 1, 9):
		if len(d[i]) != 0:
			j = bisect_left(d[i], maxi)
			ans += str(i) * (len(d[i]) - j)
			ans += str(i + 1) * j
			if d[i][-1] > maxi:
				maxi = d[i][-1]
	if m != 9:
		ans += str(9) * len(d[9])
	print(ans)


import math
testcases = int(input())
while testcases > 0:
	testcases -= 1
	numbers = '0123456789'
	string = numbers + input()
	lastinstance = 9
	temp = ''
	ans = ''
	count = string.count('0') - 1
	for i in range(count):
		ans += '0'
	for i in range(1, 9):
		counter = 0
		if string.count(numbers[i - 1]) > 0:
			lastinstance = max(lastinstance, string.rindex(numbers[i - 1]))
			temp = string[lastinstance + 1:]
			counter = temp.count(numbers[i])
			for j in range(counter):
				ans += numbers[i]
		priorrep = string.count(numbers[i]) - counter - 1
		for k in range(priorrep):
			ans += numbers[i + 1]
	count = string.count('9') - 1
	for i in range(count):
		ans += '9'
	print(ans)


import bisect

def cal(n, s):
	if n == 1:
		return s
	d = {}
	for (i, v) in enumerate(s):
		a = int(v)
		if a in d:
			d[a].append(i)
		else:
			d[a] = [i]
	nd = {}
	p = sorted(d.keys())
	for i in range(len(p)):
		if p[i] not in d:
			continue
		if p[i] not in nd:
			nd[p[i]] = len(d[p[i]])
		else:
			nd[p[i]] += len(d[p[i]])
		if d[p[i]]:
			k = d[p[i]][-1]
			for j in range(i + 1, len(p)):
				if p[j] not in d:
					continue
				tt = bisect.bisect(d[p[j]], k)
				if tt == len(d[p[j]]):
					del d[p[j]]
				else:
					d[p[j]] = d[p[j]][tt:]
				st = min(9, p[j] + 1)
				if st in nd:
					nd[st] += tt
				else:
					nd[st] = tt
	ans = ''
	for k in sorted(nd.keys()):
		ans += str(k) * nd[k]
	return ans
for jj in range(int(input())):
	s = input()
	n = len(s)
	print(cal(n, s))


import collections
import math

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_int():
	return int(input())

def inp_str():
	return input()

def solve():
	s = inp_str()
	n = len(s)
	s = list(s)
	stk = []
	top = -1
	ans = []
	for x in s:
		if len(stk) == 0:
			stk.append(x)
			top += 1
		else:
			while top >= 0 and stk[top] > x:
				temp = stk.pop()
				ans.append(str(min(9, int(temp) + 1)))
				top -= 1
			stk.append(x)
			top += 1
	ans = ans + stk
	ans.sort()
	print(''.join(ans))
tt = inp_int()
for t in range(tt):
	solve()


for _ in range(int(input())):
	s = input()
	a = list((int(x) for x in s))
	a.reverse()
	m = 10
	for i in range(len(s)):
		if a[i] > m:
			a[i] = min(a[i] + 1, 9)
		m = min(a[i], m)
	print(''.join((str(x) for x in sorted(a))))


t = int(input())

def f(mini, d, lis):
	for (i, x) in enumerate(lis):
		if x != mini:
			lis[i] = min(x + 1, 9)
	return lis
from collections import defaultdict
for i in range(t):
	s = input()
	a = [int(x) for x in s]
	n = len(s)
	d = defaultdict(list)
	for (i, x) in enumerate(s):
		d[x].append(i)
	indx = 0
	l = []
	for x in sorted(d):
		if indx < len(a):
			for y in d[x]:
				if y >= indx:
					l += f(int(x), d, a[indx:d[x][-1] + 1])
					indx = d[x][-1] + 1
					break
	l.sort()
	print(''.join([str(x) for x in l]))


import sys

def repeat(s, result):
	if len(s) == 0:
		return result
	mini = sys.maxsize
	mini = min(s)
	indices = []
	for j in range(len(s)):
		if s[j] == mini:
			indices.append(j)
	start = 0
	for j in indices:
		for x in range(start, j):
			result.append(min(s[x] + 1, 9))
		start = j + 1
	x_arr = repeat(s[indices[-1] + 1:], result)
	x_arr.sort()
	newResult = [mini] * len(indices) + x_arr
	return newResult
t = int(input())
for i in range(t):
	s = [int(_) for _ in input()]
	result = repeat(s, [])
	res = ''
	for i in result:
		res += str(i)
	print(res)


t = int(input())
for _ in range(t):
	l = [int(x) for x in list(input())]
	m = 10 ** 9
	for i in range(len(l) - 1, -1, -1):
		m = min(m, l[i])
		if l[i] > m:
			l[i] = min(l[i] + 1, 9)
	l.sort()
	print(''.join(map(str, l)))


from collections import deque

def ans(s):
	arr = list(map(int, list(s)))
	stack = deque()
	t = []
	for y in arr:
		if len(stack) == 0:
			stack.append(y)
		elif stack[-1] > y:
			while len(stack) > 0 and stack[-1] > y:
				t.append(stack.pop())
			stack.append(y)
		else:
			stack.append(y)
	t.sort()
	arr2 = []
	for y in stack:
		arr2.append(y)
	for y in t:
		arr2.append(min(y + 1, 9))
	arr2.sort()
	s = ''
	for y in arr2:
		s += str(y)
	return s
test_cases = int(input())
while test_cases != 0:
	d = input()
	print(ans(d))
	test_cases -= 1


t = int(input())
for _ in range(t):
	S = input()
	d = {}
	min_d = 9
	for i in reversed(S):
		j = int(i)
		if j < min_d:
			min_d = j
		elif j > min_d:
			j = min(j + 1, 9)
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	ans = ''
	for i in sorted(d.keys()):
		for j in range(d[i]):
			ans += str(i)
	print(ans)


for _ in range(int(input())):
	s = list(input())
	m = s[-1]
	s = s[::-1]
	ans = []
	for i in s:
		m = min(i, m)
		if i > m:
			ans.append(str(min(int(i) + 1, 9)))
		else:
			ans.append(i)
	ans.sort()
	z = ''
	for i in ans:
		z += i
	print(z)


d = {'0': '1', '1': '2', '2': '3', '3': '4', '4': '5', '5': '6', '6': '7', '7': '8', '8': '9', '9': '9'}
for _ in range(int(input())):
	s = list(input())
	n = len(s)
	a = list(range(n))
	ss = sorted(list(zip(s, a)))
	b = []
	for (i, j) in ss:
		b.append(j)
	x = 0
	for i in b:
		if x < i:
			for j in range(x, i):
				s[j] = d[s[j]]
		x = max(i + 1, x)
	print(''.join(sorted(s)))


def fun(a):
	ans = []
	rep = []
	for i in a:
		if not ans:
			ans.append(i)
		else:
			while ans and i < ans[-1]:
				x = ans.pop()
				x = min(int(x) + 1, 9)
				rep.append(str(x))
			ans.append(i)
	ans = ans + rep
	ans = list(map(int, ans))
	ans.sort()
	ans = list(map(str, ans))
	return ''.join(ans)
for _ in range(int(input())):
	a = input()
	print(fun(a))


t = int(input())
for _ in range(t):
	s = list(map(int, input()))
	if len(s) == 1:
		print(s[0])
		continue
	mapper = [0 for i in range(10)]
	for pr in range(10):
		lst_place = len(s) - 1
		mn = min(s)
		while lst_place > -1:
			if s[lst_place] == mn:
				break
			lst_place -= 1
		for i in range(lst_place + 1):
			if s[i] == mn:
				mapper[mn] += 1
			else:
				mapper[min(s[i] + 1, 9)] += 1
		s = s[lst_place + 1:]
		if not s:
			break
	for g in range(10):
		print(str(g) * mapper[g], end='')
	print()


t = int(input())
for i in range(t):
	ans = ''
	l2 = []
	l = list(map(int, list(input())))
	if l[-1] == 9:
		l2.append(9)
		l.pop(-1)
	for j in range(len(l) - 2, -1, -1):
		if l[j] == 9:
			l2.append(9)
			l.pop(j)
			j -= 1
		elif l[j] > l[j + 1]:
			l2.append(l[j] + 1)
			l.pop(j)
			j -= 1
	l += l2
	l.sort()
	l = list(map(str, l))
	for j in l:
		ans += j
	print(ans)


import collections
import sys
from typing import List
from bisect import bisect_left, bisect_right, insort_left, insort_right, insort
from collections import defaultdict, Counter, deque
from heapq import heappush, heappop
from itertools import accumulate
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
res = []
for _ in range(n):
	x = input()
	q = [d for d in x][:-1]
	q = [int(d) for d in q]
	s = []
	q2 = []
	for n in q:
		while s and s[-1] > n:
			q2.append(min(s.pop() + 1, 9))
		s.append(n)
	q2.sort()
	for n in q2:
		insort(s, n)
	res.append(''.join(map(str, s)))
for r in res:
	print(r)


for _ in range(int(input())):
	arr = [int(x) for x in input()]
	n = len(arr)
	cnt = [0] * 10
	last = [-1] * n
	prev = n - 1
	cnt[arr[n - 1]] += 1
	for i in range(n - 2, -1, -1):
		cnt[arr[i]] += 1
		if arr[i] <= arr[prev]:
			prev = i
		else:
			last[i] = prev
	i = 0
	while i < n:
		if last[i] > i:
			j = i
			while j < last[i]:
				cnt[arr[j]] -= 1
				cnt[arr[j] + (1 if arr[j] != 9 else 0)] += 1
				j += 1
			i = last[i] + 1
		else:
			i += 1
	ans = ''
	for i in range(10):
		ans += str(i) * cnt[i]
	print(ans)


from heapq import heappush, heappop
t = int(input())
for _ in range(t):
	s = input()
	h = []
	ans = []
	for c in s:
		while ans and ans[-1] > c:
			heappush(h, min(9, int(ans.pop()) + 1))
		ans.append(c)
	while h:
		ans.append(str(heappop(h)))
	ans.sort()
	print(''.join(ans))


t = int(input())
while t > 0:
	s = str(input())
	l = []
	v = []
	for i in range(0, len(s)):
		l.append(int(s[i]))
	m = l[len(l) - 1]
	v.append(m)
	for i in range(len(l) - 2, -1, -1):
		if l[i] <= m:
			m = l[i]
			v.append(m)
		else:
			v.append(min(l[i] + 1, 9))
	v.sort()
	s = ''
	for i in range(len(v)):
		s += str(v[i])
	print(s)
	t -= 1


for _ in range(int(input())):
	s = input()
	stk = []
	ans = ''
	for i in s:
		while stk != [] and stk[-1] > i:
			ans += str(min(int(stk.pop()) + 1, 9))
		stk.append(i)
	while stk:
		ans += stk.pop()
	print(''.join(sorted(ans)))


from collections import deque
for _ in range(int(input())):
	s = input()
	queue = deque()
	ans = ''
	for i in s:
		while len(queue) > 0 and queue[-1] > i:
			ans += str(min(int(queue.pop()) + 1, 9))
		queue.append(i)
	while queue:
		ans += queue.pop()
	print(''.join(sorted(ans)))


from collections import deque
for i in range(int(input())):
	ss = input()
	l = sorted(enumerate(list(ss)), key=lambda x: x[1])
	mx = 0
	t = deque()
	for (i, j) in l:
		if i < mx:
			j = str(min(int(j) + 1, 9))
		t.append(j)
		mx = max(mx, i)
	t = sorted(t)
	kk = ''.join(t)
	print(kk)


tt = int(input())
while tt:
	tt -= 1
	a = list(reversed([int(x) for x in input()]))
	mn = 100
	for i in range(len(a)):
		if a[i] > mn:
			a[i] = min(a[i] + 1, 9)
		mn = min(mn, a[i])
	print(''.join((str(x) for x in sorted(a))))


t = int(input())
for _ in range(0, t):
	s = input()
	n = len(s)
	list1 = [int(dig) for dig in s]
	list2 = [-1 for i in range(0, 10)]
	for i in range(0, n):
		list2[list1[i]] = i
	maxind = -1
	list3 = []
	for i in range(0, 10):
		if list2[i] > maxind:
			for j in range(list2[i], maxind, -1):
				if list1[j] == i or list1[j] == 9:
					list3.append(list1[j])
				else:
					list3.append(list1[j] + 1)
			maxind = list2[i]
	list3.sort()
	s1 = ''
	for i in range(0, n):
		s1 += str(list3[i])
	print(s1)


from collections import *
from bisect import *
for _ in range(int(input())):
	s = list(map(int, input()))
	d = defaultdict(list)
	n = len(s)
	for i in range(n):
		d[s[i]].append(i)
	ans = ''
	p = min(s)
	index = -1
	for i in range(10):
		for j in d[i][::-1]:
			if j > index:
				ans += str(i)
			else:
				ans += str(min(i + 1, 9))
		if d[i]:
			index = max(index, d[i][-1])
	print(ans)


for _ in range(int(input())):
	s = input()
	var = s[::-1]
	res = ''
	mini = var[0]
	for i in var:
		if int(i) > int(mini):
			res += str(min(int(i) + 1, 9))
		elif int(i) == int(mini):
			res += str(i)
		else:
			mini = i
			res += str(i)
	res = ''.join(sorted(res))
	print(res)


for _ in range(int(input())):
	s = input()
	n = len(s)
	arr = [(s[i], i) for i in range(n)]
	arr.sort()
	ans = ''
	mx = -1
	for i in arr:
		mx = max(mx, i[1])
		if i[1] < mx:
			ans += str(min(int(i[0]) + 1, 9))
		else:
			ans += i[0]
	ans = ''.join(sorted(ans))
	print(ans)


for (r2, r1, moved, s) in (([], [], [], input()) for _ in range(int(input()))):
	for digit in map(int, s):
		while r1 and digit < r1[-1]:
			moved.append(min(r1.pop() + 1, 9))
		r1.append(digit)
	(r1, moved) = (list(reversed(r1)), list(reversed(sorted(moved))))
	while r1 or moved:
		r2.append(r1.pop() if r1 and (not moved or r1[-1] < moved[-1]) else moved.pop())
	print(''.join(map(str, r2)))


t = int(input())
for ii in range(t):
	s = input()
	s = list(map(int, s))
	n = len(s)
	x = [[] for i in range(10)]
	for i in range(n):
		x[int(s[i])].append(i)
	ans = ''
	j = n - 1
	for i in range(10):
		if len(ans) == 0:
			if len(x[i]) > 0:
				ans += str(i) * len(x[i])
				j = x[i][-1]
		else:
			xx = ''
			if i == 9:
				ans += str(i) * len(x[i])
				continue
			for item in x[i]:
				if item <= j:
					xx += str(i + 1)
				else:
					xx = str(i) + xx
					j = item
			ans += xx
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	arr = []
	arr[:0] = s
	ans = [0] * 10
	arr.reverse()
	val = 9
	for i in range(len(arr)):
		if int(arr[i]) <= val:
			ans[int(arr[i])] += 1
			val = int(arr[i])
		elif int(arr[i]) < 9:
			ans[int(arr[i]) + 1] += 1
		else:
			ans[-1] += 1
	out = ''
	for i in range(10):
		while ans[i] > 0:
			out += str(i)
			ans[i] -= 1
	print(out)


for _ in range(int(input())):
	ar = [*map(str, range(10))]
	(char, s) = (max(ar), [])
	for i in reversed(input()):
		if i == '9':
			s.append(ar[9])
		elif i <= char:
			s.append(ar[int(i)])
			char = i
		else:
			s.append(ar[int(i) + 1])
	print(*sorted(s), sep='')


for s in [*open(0)][1:]:
	(*a,) = map(int, s[:-1])
	i = len(a)
	m = 9
	while i:
		i -= 1
		if a[i] <= m:
			m = a[i]
		else:
			a[i] = min(a[i] + 1, 9)
	print(*sorted(a), sep='')


cas = int(input())
for i in range(cas):
	s = input()
	num = []
	for j in range(len(s)):
		num.append(int(s[j]))
	m = num[-1]
	num = num[::-1]
	ans = []
	for x in num:
		m = min(x, m)
		if x > m:
			ans.append(min(x + 1, 9))
		else:
			ans.append(x)
	ans.sort()
	res = ''
	for v in range(len(ans)):
		res = res + str(ans[v])
	print(res)


def main():
	t = int(input())
	for _ in range(t):
		(*s,) = map(int, list(input()))
		m = s[-1]
		ans = []
		for i in reversed(s):
			m = min(i, m)
			ans.append(i if i <= m else min(i + 1, 9))
		print(*sorted(ans), sep='')
main()


for _ in range(int(input())):
	(io, mn) = ([*map(int, input())], [])
	itr = io[-1]
	for ele in reversed(io):
		if ele > itr:
			mn.append(min(ele + 1, 9))
		else:
			mn.append(ele)
			itr = ele
	print(*sorted(mn), sep='')


tests = int(input())
for t in range(tests):
	s = input()
	arr = []
	for i in range(len(s)):
		arr.append((int(s[i]), i))
	arr.sort()
	prev = arr[0][1]
	for i in range(1, len(s)):
		cur = arr[i]
		if cur[1] > prev:
			prev = cur[1]
		else:
			arr[i] = (min(cur[0] + 1, 9), cur[0])
	arr.sort()
	ans = ''
	for (num, idx) in arr:
		ans += str(num)
	print(ans)


l = int(input())
for j in range(l):
	s = input()
	lst = []
	d = {}
	counter = {}
	for i in range(len(s)):
		lst.append((s[i], i))
	l = []
	(p1, p2) = (len(lst) - 1, len(lst) - 2)
	flag = False
	while not flag:
		flag = True
		while p2 >= 0 or p1 >= 0:
			l.append(lst[p1])
			while p2 >= 0 and lst[p2][0] > lst[p1][0]:
				flag = False
				p2 -= 1
			p1 = p2
			p2 -= 1
		temp = lst
		lst = l
		l = []
	sett = set()
	for i in temp:
		if i[0] != '9':
			sett.add(i[1])
	ans = []
	a = []
	for i in range(len(s)):
		if i in sett:
			a.append(s[i])
		else:
			ans.append(str(min(9, int(s[i]) + 1)))
	a += ans
	a.sort()
	answer = ''.join(a)
	print(answer)