Numeric Keypad

the first line contains an integer T, the number of testcases.
Each testcase occupies a single line with an integer K.

For 50%of the data ,1<=K<=999.
For 100% of the data, 1<=K<=10^500,t<=20.

for each testcase output one line, the maximum number less than or equal to the corresponding K that can be produced.

3
25
83
131

25
80
129

# -*- encoding: utf8 -*-
"""
二维列表pad表示当前行值对应的数字下一次可以按的数字列在第二维度上
一维列表last表示当前数字的下一次按键可用数字数-1，方便循环进行了-1

举例解析：
数字：131
把1输入，
从3开始查找，有3种情况：
 1) 找到need，那么查找下一个字符
 2) 找不到need，那么试着去找第一个小于need的数，之后的数字就选择当前最大的合法值，结束并返回
 3) 连小于need的数都找不到，就像这个例子：在key=3的时候，找need=1，找不到，这个时候，
需要回到key=1的时候(去掉ret最后的字符，字符串变空需要特殊处理)，找1可用的数组里比3小的
数字(不能直接-1，因为可能不在可用范围内)。之后的数字填充最大的合法值，结束并返回。
"""

# mapping table
pad = [[0],
		   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
		   [0, 2, 3, 5, 6, 8, 9],
		   [3, 6, 9],
		   [0, 4, 5, 6, 7, 8, 9],
		   [0, 5, 6, 8, 9],
		   [6, 9],
		   [0, 7, 8, 9],
		   [0, 8, 9],
		   [9]]
last = [0, 9, 6, 2, 6, 4, 1, 3, 2, 0]

def find_min_number(num):
	"""
	find the minimum number
	"""
	ret = []
	input_str = str(num)
	input_length = len(input_str)
	ret.append(input_str[0])
	i = 1
	while i < input_length:
		need = int(input_str[i])
		key = int(ret[-1])
		j = last[key]
		# Situation 1)
		while j >= 0:
			if pad[key][j] == need:
				i += 1
				ret.append(str(pad[key][j]))
				break
			j -= 1 

		# Situation 2)
		if j < 0:
			j = last[key]
			while j >= 0:
				if pad[key][j] < need:
					ret.append(str(pad[key][j]))
					key = int(ret[-1])
					return ''.join(ret) + str(pad[key][last[key]])*(input_length-len(ret))
				j -= 1

		# Situation 3)
		if j < 0:
			need = key
			ret = ret[0:-1]
			if len(ret) == 0:
				ret.append(str(need-1))
				key = int(ret[-1])
				return ''.join(ret) + str(pad[key][last[key]])*(input_length-len(ret))

			key = int(ret[-1])
			j = last[key]
			while j >= 0:
				if pad[key][j] < need:
					ret.append(str(pad[key][j]))
					key = int(ret[-1])
					return ''.join(ret) + str(pad[key][last[key]])*(input_length-len(ret))
				j -= 1
	return ''.join(ret)

T = raw_input()
intT = int(T)

for i in range(intT):
	n = raw_input()
	num = int(n)
	print find_min_number(num)