There is an integer $n$ without zeros in its decimal representation. Alice and Bob are playing a game with this integer. Alice starts first. They play the game in turns.

On her turn, Alice must swap any two digits of the integer that are on different positions. Bob on his turn always removes the last digit of the integer. The game ends when there is only one digit left.

You have to find the smallest integer Alice can get in the end, if she plays optimally.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first and the only line of each test case contains the integer $n$ ($10 \le n \le 10^9$) — the integer for the game. $n$ does not have zeros in its decimal representation.


-----Output-----

For each test case output a single integer — the smallest integer Alice can get in the end of the game.


-----Examples-----

Input
3
12
132
487456398
Output
2
1
3


-----Note-----

In the first test case Alice has to swap $1$ and $2$. After that Bob removes the last digit, $1$, so the answer is $2$.

In the second test case Alice can swap $3$ and $1$: $312$. After that Bob deletes the last digit: $31$. Then Alice swaps $3$ and $1$: $13$ and Bob deletes $3$, so the answer is $1$.

Difficulty: EASY
Tags: String algorithms

Game theory

Mathematics

Constructive algorithms

Starter code:

Solutions:
for s in [*open(0)][1:]:
	print(min(s[len(s) < 4:-1]))


import sys
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
	n = list(input().strip())
	while len(n) != 1:
		if len(n) == 2:
			n = n[1]
			break
		else:
			n = min(n)
	sys.stdout.write(str(n) + '\n')


for i in [*open(0)][1:]:
	print(min(i[len(i) < 4:-1]))


for kvs in [*open(0)][1:]:
	print(min(kvs[len(kvs) < 4:-1]))


result = ''
number = int(input())
for x in range(number):
	string = input()
	strings = []
	for y in string:
		if y not in strings:
			strings.append(y)
	strings.sort()
	if len(string) == 2:
		result += string[1] + '\n'
	else:
		result += strings[0] + '\n'
print(result[:-1])


from sys import stdin, stdout
I = stdin.readline
O = stdout.write
for _ in range(int(I())):
	n = int(I())
	st = str(n)
	if len(st) == 2:
		st = st[::-1]
		print(int(st[0]))
	else:
		print(int(min(st)))


for s in [*open(0)][1:]:
	print((min(s[:-1]), s[1])[int(s) < 100])


import sys
n = int(sys.stdin.readline())
for _ in range(n):
	num = sys.stdin.readline().rstrip()
	if len(num) == 2:
		print(num[1])
	else:
		print(min(num))


def dig_min(val):
	if len(val) > 2:
		return min((int(i) for i in val))
	return val[-1]
ret = ''
n = int(input())
for i in range(n):
	ret += str(dig_min(input())) + '\n'
print(ret)


def main():
	input_number_test_case = input()
	number_test_cases = int(input_number_test_case)
	test_cases = []
	for index in range(number_test_cases):
		test_case = input()
		test_cases.append(test_case)
	get_result(test_cases)

def get_result(test_cases):
	for test_case in test_cases:
		digits = [int(digit) for digit in test_case]
		if len(test_case) == 2:
			print(digits[-1])
		else:
			digits.sort()
			print(digits[0])
main()


results = []
for _ in range(int(input())):
	n = input()
	if len(n) < 3:
		result = n[-1]
	else:
		result = min(n, key=int)
	results.append(result)
print('\n'.join(results))


import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	j = list(input())
	if len(j) < 3:
		print(j[-1])
	else:
		print(min(j))


t = int(input())
out = ''
for _ in range(t):
	arr = [int(x) for x in input()]
	if len(arr) == 1:
		out += str(arr[0]) + '\n'
	elif len(arr) == 2:
		out += str(arr[1]) + '\n'
	else:
		out += str(min(arr)) + '\n'
print(out)


n = int(input())
l = []
for i in range(n):
	t = int(input())
	l.append(t)
for i in l:
	s = str(i)
	if len(s) > 2:
		print(int(min(s)))
	elif len(s) == 2:
		print(int(s[1]))
	else:
		print(int(s[0]))


import sys
input = sys.stdin.readline

def solve():
	s = list(input().strip())
	n = len(s)
	if n == 2:
		return s[1]
	else:
		return min(s)
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline
tcs = int(input().strip())
for tc in range(tcs):
	n = list(input())[:-1]
	if len(n) == 2:
		print(n[-1])
	else:
		print(min(n))


t = int(input())
ans = []
for x in range(t):
	n = input()
	if len(n) == 2:
		ans.append(n[1])
		continue
	ch = list(n)
	ans.append(min(ch))
for a in ans:
	print(a)


lis = []
for i in range(int(input())):
	a = int(input())
	b = str(a)
	if len(b) == 2:
		c = b[1]
	else:
		c = min(b)
	lis.append(c)
print(*lis, sep='\n')


def out(m):
	if len(m) == 2:
		return m[1]
	else:
		return min(m)
t = int(input())
list1 = []
for i in range(t):
	n = list(input())
	a = out(n)
	list1.append(a)
for k in list1:
	print(k)


for i in range(int(input())):
	a = input()
	if len(a) == 2 and a[0] == min(a):
		print(a[1])
	else:
		print(min(a))


for i in range(int(input())):
	n = input()
	if len(n) != 2:
		print(min(n))
	else:
		print(n[1])


lines = []
while True:
	try:
		a = input()
		lines.append(a)
	except:
		break
notest = int(lines[0])
i = 1
while i <= notest:
	no = lines[i]
	min = int(no[0])
	j = 0
	minpos = 0
	for j in range(0, len(no)):
		if int(no[j]) < min:
			min = int(no[j])
			minpos = j
	if minpos == len(no) - 2 and len(no) == 2:
		print(int(no[1]))
	else:
		print(min)
	i += 1


n = int(input())
a = []
for i in range(n):
	b = str(input())
	a.append(b)
for i in range(n):
	c = 9
	for j in a[i]:
		if c > int(j):
			c = int(j)
	if len(a[i]) == 1:
		print(a[i])
	elif len(a[i]) == 2:
		print(int(a[i][1]))
	else:
		print(c)


t = int(input())
while t:
	t -= 1
	n = input()
	if len(n) < 3:
		print(n[-1])
	else:
		tmp = ''.join(sorted(n))
		print(tmp[0])


def smallest_numbr(numbr):
	minnum = 11
	while numbr > 0:
		minnum = min(minnum, numbr % 10)
		numbr //= 10
		if minnum == 1:
			return minnum
	return minnum
n = int(input())
answer = []
for _ in range(n):
	number = input()
	if len(number) == 2:
		answer.append(number[1])
	else:
		answer.append(smallest_numbr(int(number)))
for elem in answer:
	print(elem)


import sys
n = int(sys.stdin.readline())
for i in range(n):
	number = list(sys.stdin.readline())
	for j in range(len(number)):
		if number[j] == '\n':
			number.remove(number[j])
		else:
			number[j] = int(number[j])
	i = len(number)
	if i == 2:
		print(number[1])
	else:
		print(min(number))


for _ in range(int(input())):
	n = input()
	if len(n) == 2:
		n = int(n)
		print(n % 10)
	else:
		arr = [x for x in n]
		print(min(arr))


def split(word):
	return [int(char) for char in word]
for _ in range(int(input())):
	num = input()
	lst = split(num)
	if len(lst) == 2:
		print(lst[1])
	else:
		print(min(lst))


l1 = []
l2 = []
l3 = []
t = int(input())
for i in range(t):
	a = input()
	count = -1
	l1 = []
	for i in a:
		l1.append(int(i))
	if len(a) == 2:
		l2.append(l1[1])
	else:
		l2.append(min(l1))
for i in l2:
	print(i)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	if n == 2:
		print(s[1])
	else:
		res = sorted(s)
		print(res[0])


for i in range(int(input())):
	st = input()
	if st.__len__() == 2:
		print(st[1])
	elif '1' in st:
		print(1)
	elif '2' in st:
		print(2)
	elif '3' in st:
		print(3)
	elif '4' in st:
		print(4)
	elif '5' in st:
		print(5)
	elif '6' in st:
		print(6)
	elif '7' in st:
		print(7)
	elif '8' in st:
		print(8)
	else:
		print(9)


def solve(n):
	nl = list(n)
	if len(nl) == 2:
		return nl[1]
	return min(nl)
t = int(input())
for i in range(t):
	n = input()
	print(solve(n))


for t in range(int(input())):
	s = input()
	if len(s) == 2:
		print(s[1])
	else:
		print(min(s))


n = int(input())
s = [list(map(int, input())) for i in range(n)]
for i in s:
	i[0] = min(i)
	while len(i) > 1:
		if len(i) == 2:
			(i[0], i[1]) = (i[1], i[0])
		if len(i) == 3:
			i[1] = min(i)
		del i[-1]
	print(*i)


t = int(input())
for _ in range(t):
	n = input()
	print(min(n) if len(n) > 2 else n[-1])


n = int(input())
l = []
for i in range(n):
	l.append(int(input()))
for x in l:
	if len(str(x)) == 2:
		print(str(x)[-1])
	else:
		print(min([int(y) for y in str(x)]))


n = int(input())
while n > 0:
	t = input()
	if len(t) > 2:
		print(min(t))
	else:
		print(t[-1:])
	n -= 1


T = int(input())
for i in range(T):
	s = input()
	if len(s) == 2:
		print(s[1])
	else:
		print(min(s))


import math
result = []

def finding_result(lst):
	if len(lst) == 2:
		lst.reverse()
		result.append(lst[0])
	elif len(lst) > 2:
		lst.sort()
		result.append(lst[0])

def main():
	test_cases = int(input())
	i = 0
	j = 0
	while i < test_cases:
		number_list = []
		number = int(input())
		while number > 10:
			div_result = number % 10
			number_list.append(div_result)
			number = math.floor(number / 10)
		number_list.append(number)
		number_list.reverse()
		finding_result(number_list)
		i = i + 1
	while j < test_cases:
		print(result[j], '\n')
		j = j + 1
main()


T = int(input())
for i in range(T):
	val = input()
	lisval = list(val)
	if len(lisval) == 2:
		print(lisval[1])
	else:
		lisval.sort()
		print(lisval[0])


a = int(input())
while a:
	b = str(input())
	if len(b) > 2:
		print(min(b))
	elif len(b) == 2:
		print(b[1])
	else:
		print(b[0])
	a -= 1


n = int(input())
for i in range(n):
	a = input()
	if len(a) == 2 and a.index(max(a)) == 1:
		print(max(a))
	else:
		print(min(a))


tc = int(input())
for _ in range(tc):
	a = list(input())
	if len(a) == 2:
		print(a[1])
	else:
		print(min(a))


for i in range(int(input())):
	num = int(input())
	s = str(num)
	if len(s) > 2:
		print(min(s))
	else:
		print(s[1])


for i in range(int(input())):
	b = input()
	c = int(b)
	if len(b) == 2:
		print(b[1])
	else:
		print(min(b))


for _ in range(int(input())):
	N = list(input())
	if len(N) == 2:
		print(N[-1])
	else:
		print(min(N))


n = int(input())
for i in range(n):
	a = str(input())
	if len(a) == 1:
		print(a)
	elif len(a) == 2:
		print(a[-1])
	else:
		print(min(a))