Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

One day, Chef's friend gave him a wrong number $W$ containing $N + 1$ digits and said that the actual number $A$ is the largest possible number that can be obtained from deleting exactly one digit of $W$. Chef was able to find $A$ but forgot $W$. 

Given $A$, find the smallest possible number $W$ of length $N + 1$ without leading $0$'s that is consistent with the story above. We can show that there is always at least one such $W$ consistent with the story.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
Each test case contains a single line of input, an integer $A$. 

------ Output ------
For each testcase, output in a single line string representing the answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 100$
$0 ≤ A_{i} ≤ 9$ for all valid $i$, where $A_{i}$ denotes the $i$-th digit of $A$
$A_{1} \neq 0$ (no leading zero)
$10 ≤ |A| ≤ 5000$, where $|A|$ denotes the number of digits of $A$

------ Subtasks ------
Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
2
9876543211
12345678999
----- Sample Output 1 ------ 
19876543211
102345678999
----- explanation 1 ------ 
It can be proven that the above output strings are the smallest possible numbers from which you can arrive at the correct number in the input.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	A = int(input())
	k = list(str(A))
	if k[0] == '1':
		k.insert(1, '0')
	else:
		k.insert(0, '1')
	print(int(''.join(k)))


for i in range(int(input())):
	s = input()
	if s[0] == '1':
		st = '1' + '0' + s[1:]
	else:
		st = '1' + s
	print(st)


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in str(n)]
	if l[0] == 1:
		l.insert(1, 0)
	else:
		for i in range(2, 10):
			if l[0] == i:
				l.insert(0, 1)
	print(''.join(map(str, l)))


for _ in range(int(input())):
	s = input()
	if s[0] == '1':
		print(s[0] + '0' + s[1:])
	else:
		print('1' + s)


t = int(input())
while t:
	s = input()
	if s[0] != '1':
		print('1' + s[0:])
	else:
		print(s[0] + '0' + s[1:])
	t -= 1


for i in range(int(input())):
	s = input()
	if s[0] == '1':
		s1 = '0'
		res = s[:1] + s1 + s[1:]
		print(str(res))
	else:
		print('1' + s)


t = int(input())
for i in range(t):
	s = input()
	s1 = '1' + s
	s2 = s[0] + '0' + s[1:len(s):1]
	s1 = int(s1)
	s2 = int(s2)
	if s1 > s2:
		print(s2)
	else:
		print(s1)


q = int(input())
while q > 0:
	n = input()
	m = '1' + n
	s = n[0] + '0' + n[1:]
	if m > s:
		print(s)
	else:
		print(m)
	q = q - 1


t = int(input())
for i in range(t):
	z = input()
	if z[0] == '1':
		x = '10' + z[1:]
	else:
		x = '1' + z
	print(x)


def read_input():
	t = int(input())
	tl = [input() for _ in range(t)]
	return (tl, t)

def solve(N):
	n0 = int(N[0])
	n0 = 10 if n0 == 1 else 1 * 10 + n0
	return str(n0) + N[1:]
(tl, t) = read_input()
for i in range(t):
	print(solve(tl[i]))


for _ in range(int(input())):
	l = input()
	l = [*l]
	if l[0] == '1':
		l.insert(1, '0')
	else:
		l.insert(0, '1')
	print(''.join(l))


t = int(input())
for ni in range(t):
	s = input()
	if int(s[0]) > 1:
		s = '1' + s
	else:
		s = '1' + '0' + s[1:]
	print(s)


t = int(input())
for i in range(t):
	a = input()
	if int(a[0]) > 1:
		a = '1' + a
	else:
		a = '1' + '0' + a[1:]
	print(a)


for t in range(int(input())):
	w = input()
	print('1' + w if 1 < int(w[0]) else w[0] + '0' + w[1:])


for _ in range(int(input())):
	A = input()
	print('1' + A if A[0] != '1' else '10' + A[1:])


t = int(input())
while t != 0:
	n = input()
	if n[0] == '1':
		print('1' + '0' + n[1:])
	else:
		print('1' + n)
	t -= 1


for _ in range(int(input())):
	a = input()
	if int(a[0]) > 1:
		print('1' + str(a))
	else:
		print(a[0] + '0' + a[1:])


for tc in range(int(input())):
	a = input()
	if int(a[0]) > 1:
		print('1' + a)
	else:
		print(a[0] + '0' + a[1:])


for _ in range(int(input())):
	a = int(input())
	b = str(a)
	c = '1' + b
	c1 = int(c)
	d = b[0] + '0' + b[1:]
	d1 = int(d)
	print(min(c1, d1))


for i in range(int(input())):
	n = int(input())
	x = str(n)
	if x[0] == '1':
		print(x[0] + '0' + x[1:])
	else:
		print('1' + x)


for t in range(int(input())):
	s = input()
	if s[0] == '1':
		x = '10' + s[1:]
	else:
		x = '1' + s
	print(x)


for _ in range(int(input())):
	n = input()
	if n[0] != '1':
		print('1' + n)
	else:
		n = '1' + '0' + n[1:]
		print(n)


for _ in range(int(input())):
	x = input()
	if x[0] == '1':
		print(x[0] + '0' + x[1:])
	else:
		print('1' + x)


t = int(input())
for i in range(t):
	a = str(input())
	if int(a[0]) > 1:
		print('1' + a)
	else:
		s = list(a)
		s.insert(1, 0)
		r = str(s).replace('[', '').replace(']', '').replace("'", '').replace(' ', '').replace(',', '')
		print(r)


for _ in range(int(input())):
	a = int(input())
	a = str(a)
	a = list(a)
	if a[0] != '1':
		a.insert(0, '1')
	elif a[0] == '1':
		a.insert(1, '0')
	print(int(''.join(a)))


for _ in range(int(input())):
	n = list(input())
	if n[0] == '1':
		n.insert(1, '0')
	elif int(n[0]) > 1:
		n.insert(0, '1')
	x = ''.join(n)
	print(x)


for i in range(int(input())):
	a = input()
	l = []
	l1 = []
	for j in a:
		l.append(j)
	for j in range(len(l)):
		if l[j] != '1' and j == 0:
			l1 = [str(1)] + l
			break
		elif j != 0:
			l1 = l[0:j] + [str(0)] + l[j:len(l)]
			break
	for j in l1:
		print(j, end='')
	print()


t = int(input())
while t:
	s = input()
	res = ''
	if s[0] > '1':
		res = '1' + s
	else:
		res = '10' + s[1:]
	print(res)
	t -= 1


t = int(input())
for test in range(t):
	n = input()
	if n[0] == '1':
		ans = '10' + n[1:]
	else:
		ans = '1' + n
	print(ans)


for i in range(int(input())):
	a = int(input())
	s = str(a)
	if int(s[0]) > 1:
		print('1' + s)
	else:
		print(s[0] + '0' + s[1:len(s)])


t = int(input())
for i in range(t):
	k = list(input())
	if k[0] == '1':
		k.insert(1, '0')
	else:
		k.insert(0, '1')
	print(''.join(k))


testcases = int(input())
for i in range(testcases):
	arr = input()
	string = str(arr)
	if string[0] == '1':
		string = string[0] + '0' + string[1:]
	else:
		string = '1' + string[:]
	print(string)


import random
t = int(input())
for i in range(0, t):
	a = input()
	ans = len(a)
	a = int(a)
	n = str(a)
	s1 = 10 ** ans + a
	s2 = n[0] + '0' + n[1:]
	s2 = int(s2)
	print(min(s1, s2))


for _ in range(int(input())):
	A = list(input().strip())
	if A[0] == '1':
		A.insert(1, '0')
	else:
		A.insert(0, '1')
	print(''.join(A))


t = int(input())
for i in range(0, t):
	s = input()
	ans = len(s)
	if int(s[0]) > 1:
		s1 = '1' + s[:]
	elif s[0] == '1':
		s1 = s[0] + '0' + s[1:]
	print(s1)


vishnesh = int(input())
for i in range(vishnesh):
	n = input()
	a = len(n)
	p = int(n)
	s1 = 10 ** a + p
	s2 = n[0] + '0' + n[1:]
	s2 = int(s2)
	print(min(s1, s2))


t = input()
for c in range(0, int(t)):
	a = input()
	arr = []
	for x in a:
		arr.append(int(x))
	out = ''
	if arr[0] != 1:
		out = '1' + a
	else:
		for y in range(0, len(a)):
			out = out + a[y]
			if y == 0:
				out = out + '0'
	print(out)


q = int(input())
while q > 0:
	q -= 1
	num = input()
	temp = ''
	if num[0] == '1':
		temp = '10' + num[1:]
	else:
		temp = '1' + num
	print(temp)


T = int(input())
for tc in range(T):
	W = int(input())
	s = str(W)
	if 1 < int(s[0]) < 10:
		s = '1' + s
	else:
		s = '10' + s[1:]
	print(s)


for _ in range(int(input())):
	n = input()
	res = ''
	if int(n[0]) > 1:
		res += '1'
		res += n
	elif int(n[0]) == 1:
		res += '1'
		for i in range(1, len(n)):
			if int(n[i]) > 0:
				res += '0'
				res += n[i:]
				break
	print(res)


t = int(input())
for i in range(t):
	case = input()
	l = ''
	if case[0] != '1':
		l += '1' + case[0]
		l += case[1:]
	else:
		l += case[0] + '0'
		l += case[1:]
	print(l)


for _ in range(int(input())):
	n = int(input())
	n = str(n)
	if n[0] != '1':
		s = '1' + n
		print(s)
	else:
		s = '10' + n[1:]
		print(s)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(n)
	if s[0] == '1':
		print(int(s[0] + '0' + s[1:]))
	else:
		print(int('1' + s))


tests = int(input())
for i in range(tests):
	num = input()
	ans = ''
	if num[0] == '1':
		ans = num[0] + '0' + num[1:]
	else:
		ans = '1' + num
	print(ans)


t = int(input())
while t != 0:
	s1 = input()
	s2 = ''
	if s1[0] == '1':
		s2 = s1[0] + '0' + s1[1:]
		print(s2)
	else:
		s2 = '1' + s1
		print(s2)
	t -= 1


for _ in range(int(input())):
	a = input()
	if a[0] == '1':
		print(int(a) + pow(10, len(a)) - pow(10, len(a) - 1))
	else:
		print(int(a) + pow(10, len(a)))


T = int(input())

def algo():
	A = input()
	if A[0] != '1':
		print('1' + A)
	else:
		print('10' + A[1:])
for i in range(T):
	algo()


for _ in range(int(input())):
	a = input()
	if not a.startswith('1'):
		print('1' + a)
	else:
		print(a[:1] + '0' + a[1:])


def solution(num):
	if not num.startswith('1'):
		return '1' + num
	else:
		return num[:1] + '0' + num[1:]
for i in range(0, int(input())):
	print(solution(input()))


tc = int(input())
for i in range(tc):
	number = str(input())
	if number[0] == '1':
		test = number[0] + '0' + number[1:]
		print(int(test))
	else:
		print(int('1' + number[0:]))


t = int(input())
for i in range(t):
	s = input()
	ans = ''
	if s[0] == '1':
		ans += s[0] + '0' + s[1:]
	else:
		ans += '1' + s
	print(ans)


a = int(input())
for i in range(a):
	n = input()
	k = ''
	if n[0] > '1':
		k += '1' + n
	else:
		k += '10' + n[1:]
	print(k)


ujju = int(input())
for jyo in range(ujju):
	sed = input()
	if int(sed[0]) != 1:
		print('1' + sed)
	else:
		print('10' + sed[1:])


t = int(input())
for i in range(t):
	s = input()
	w = ''
	if s[0] > '1':
		w += '1' + s
	else:
		w += '10' + s[1:]
	print(w)