Vasya learned about integer subtraction in school. He is still not very good at it, so he is only able to subtract any single digit number from any other number (which is not necessarily single digit).
For practice, Vasya chose a positive integer n$n$ and wrote it on the first line in his notepad. After that, on the second line he wrote the result of subtraction of the first digit of n$n$ from itself. For example, if n=968$n = 968$, then the second line would contain 968−9=959$968 - 9 = 959$, while with n=5$n = 5$ the second number would be 5−5=0$5 - 5 = 0$. If the second number was still positive, then Vasya would write the result of the same operation on the following line, and so on. For example, if n=91$n = 91$, then the sequence of numbers Vasya would write starts as follows: 91,82,74,67,61,55,50,…$91, 82, 74, 67, 61, 55, 50, \ldots$. One can see that any such sequence eventually terminates with the number 0$0$.
Since then, Vasya lost his notepad. However, he remembered the total number k$k$ of integers he wrote down (including the first number n$n$ and the final number 0$0$). What was the largest possible value of n$n$ Vasya could have started with?

-----Input:-----
The first line contains T$T$ , number of test cases per file.
The only line in each testcase contains a single integer k−$k-$ the total number of integers in Vasya's notepad (2≤k≤1012$2 \leq k \leq 10^{12}$).

-----Output:-----
Print a single integer−$-$ the largest possible value of the starting number n$n$. It is guaranteed that at least one such number n$n$ exists, and the largest possible value is finite.

-----Constraints-----
- 1≤T≤34$1 \leq  T \leq 34 $
- 2≤k≤1012$2 \leq k \leq 10^{12}$

-----Sample Input-----
3
2
3
100

-----Sample Output:-----
9
10
170

Difficulty: HARD

Starter code:

Solutions:
def getAns(num):
	if num < 10:
		return 2
	last = int(str(num)[0])
	rem = int(str(num)[1:])
	steps = 2
	p = len(str(num)) - 1
	while True:
		steps += rem // last + 1
		rem = rem % last
		if last > 0:
			rem = rem + 10 ** p - last
		last = last - 1
		if last == 0:
			p = p - 1
			last = 9
			if len(str(rem)) == 1:
				rem = 0
			else:
				rem = int(str(rem)[1:])
		if rem == 0:
			break
	return steps
for awa in range(int(input())):
	k = int(input())
	if k == 1:
		print(0)
	elif k == 2:
		print(9)
	elif k == 3:
		print(10)
	else:
		(low, high, ans) = (0, 10 ** 18, 0)
		while low <= high:
			mid = (low + high) // 2
			temp = getAns(mid)
			if int(temp) == k:
				ans = max(ans, mid)
				low = mid + 1
			elif temp < k:
				low = mid + 1
			else:
				high = mid - 1


def findsubtract(num):
	n = num
	strn = str(n)
	count = 0
	while n > 0:
		fd = int(strn[0])
		p = len(strn) - 1
		if p == 0:
			n -= fd
			strn = str(n)
			count += 1
		else:
			n1 = n - fd * 10 ** p
			n2 = n1 // fd + 1
			count += n2
			n -= n2 * fd
			strn = str(n)
	return count + 1
for i in range(int(input())):
	k = int(input())
	if k == 2:
		print(9)
		continue
	n = None
	brutetop = 4 * k
	brutebottom = 0
	while abs(brutetop - brutebottom) > 20:
		v = round((brutetop + brutebottom) / 2)
		t = findsubtract(v)
		if t <= k:
			brutebottom = v
		else:
			brutetop = v
	for j in range(brutetop, brutebottom - 1, -1):
		n = findsubtract(j)
		if n == k:
			print(j)
			break


import sys
T = int(sys.stdin.readline())

def nearest_nine(max):
	ps = 0
	for j in range(9, 0, -1):
		mstr = str(max)
		lp = int(mstr[1:])
		lp = lp // j
		ps += lp + 1
		max -= (lp + 1) * j
	return ps
all9 = [2]
for i in range(1, 13):
	max = 10 ** (i + 1) - 1
	all9.append(all9[i - 1] + nearest_nine(max))
for i in range(T):
	k = int(sys.stdin.readline())
	for (i, item) in enumerate(all9):
		if item == k:
			result = 10 ** (i + 1) - 1
			break
		elif item < k:
			continue
		else:
			k -= all9[i - 1]
			deg = 10 ** i
			result = deg - 1
			fd = 1
			while True:
				hl = (deg - 1) * (fd + 1)
				if result + k * fd < hl:
					result += k * fd
					break
				else:
					incr = (hl - result) // fd
					k -= incr
					result += fd * incr
					if (hl - result) % fd:
						k -= 1
						result += fd
					fd += 1
			break
	print(result)


t = int(input())
for m in range(t):

	def diff(n):
		count = 1
		while n != 0:
			n -= int(str(n)[0])
			count += 1
		return count
	hash = {}
	for i in range(9, 1001):
		z = diff(i)
		hash[z] = i
	lim = 10 ** 13
	k = 100
	ranges = {}
	for i in hash.keys():
		ranges[hash[i]] = i
	ans = {100: 30}
	while k <= lim:
		z = str(k)
		diff = int(str(k)[0])
		g = (int(z[0]) + 1) * 10 ** (len(z) - 1)
		g = str(g)
		if diff != 9:
			for f in range(int(g) - 10, int(g)):
				if (f - k) / diff == (f - k) // diff:
					if str(f + int(z[0]) + 1)[0] == g[0]:
						break
			u = (f - k) // diff + 1
			ans[f + int(z[0]) + 1] = u + ans[k]
			k = f + int(z[0]) + 1
		else:
			f = int('9' * len(z))
			u = (f - k) // diff + 1
			ans[int('9' * len(z)) + 1] = u + ans[k] + 1
			k = int('9' * len(z)) + 1
	n = int(input())

	def p1(n, hash):
		if n > 30:
			v = list(ans.keys())
			for i in range(len(ans.keys()) - 1):
				if ans[v[i]] <= n < ans[v[i + 1]]:
					diff = int(str(v[i])[0])
					n = n - ans[v[i]]
					z = n * diff + v[i]
					if diff == 9 and z > v[i + 1]:
						return int('9' * len(str(v[i])))
					else:
						return z
		elif n != 1:
			return hash[n]
		else:
			return 0
	print(p1(n, hash))


lim = 10 ** 12
fix = [(9, 2), (10, 3)]
pk = 3
p10 = 10
while pk <= lim:
	k = pk
	v = p10
	over = 0
	for ld in range(1, 9):
		step = (p10 - 2 - over) // ld + 1
		v += step * ld + 1
		k += step
		fix.append((v, k))
		over = v % 10
	pf = p10 * 10 - 1
	v = pf
	k = 0
	for ld in reversed(range(2, 10)):
		step = v % p10 // ld + 1
		v -= step * ld
		k += step
	pk += k + v % p10
	fix.append((pf, pk))
	pk += 1
	p10 *= 10
	fix.append((p10, pk))
for ti in range(int(input())):
	k = int(input())
	lo = 0
	hi = len(fix)
	while hi - lo > 1:
		md = (hi + lo) // 2
		if fix[md][1] > k:
			hi = md
		else:
			lo = md
	(val, s) = fix[lo]
	if s == k:
		print(val)
	else:
		lead = lo % 10
		print(val + lead * (k - s))


def find_steps_number(target_steps=30):
	steps = 3
	step_distance = 1
	power = 10
	modulo = 9
	step_list = [power]
	steps_number_dict = {2: 9, 3: 10}
	while steps < target_steps:
		while step_distance < 10 and steps < target_steps:
			temp_list = []
			for result in step_list:
				if result % modulo == 0:
					result1 = result + step_distance
					temp_list.append(result1)
					step_distance += 1
					if step_distance < 10:
						result2 = result + step_distance
						temp_list.append(result2)
				elif step_distance < 10:
					result += step_distance
					temp_list.append(result)
			step_list = temp_list[:]
			steps += 1
			steps_number_dict[steps] = max(step_list)
		steps += 1
		step_distance = 1
		power *= 10
		step_list = [power]
		modulo = modulo * 10 + 9
		if steps <= target_steps:
			steps_number_dict[steps] = max(step_list)
	return steps_number_dict

def create_stepNumber_dict(steps_number_dict):
	starting_step = 30
	limit = 10 ** 13
	starting_number = steps_number_dict[starting_step]
	test_dict = {len(str(starting_step)): {starting_step: starting_number}}
	cumalative_steps = starting_step
	test_dict[len(str(starting_number))] = {starting_number: starting_number + starting_number - cumalative_steps}
	test_dict[len(str(cumalative_steps))][int('9' * len(str(cumalative_steps)))] = starting_number + int('9' * len(str(cumalative_steps))) - cumalative_steps
	while starting_number <= limit:
		starting_number_string = str(starting_number)
		first_digit = int(starting_number_string[0])
		ending_number = (first_digit + 1) * 10 ** (len(starting_number_string) - 1)
		ending_number_string = str(ending_number)
		if first_digit < 9:
			for jump_number in range(ending_number - first_digit - 1, ending_number):
				if (jump_number - starting_number) / first_digit == (jump_number - starting_number) // first_digit:
					if str(jump_number + first_digit + 1)[0] == ending_number_string[0]:
						break
			steps = (jump_number - starting_number) // first_digit + 1
			cumalative_steps += steps
			test_dict[len(str(cumalative_steps))] = test_dict.get(len(str(cumalative_steps)), {})
			test_dict[len(str(cumalative_steps))][cumalative_steps] = test_dict.get(cumalative_steps, jump_number + first_digit + 1)
			starting_number = jump_number + first_digit + 1
		else:
			jump_number = int('9' * len(starting_number_string))
			steps = (jump_number - starting_number) // first_digit + 1
			cumalative_steps += steps + 1
			test_dict[len(str(cumalative_steps))] = test_dict.get(len(str(cumalative_steps)), {})
			test_dict[len(str(cumalative_steps))][cumalative_steps] = test_dict.get(cumalative_steps, jump_number + 1)
			number_steps = jump_number + 1
			tens_steps = jump_number + 1 + jump_number + 1 - cumalative_steps
			test_dict[len(str(number_steps))] = test_dict.get(len(str(number_steps)), {})
			test_dict[len(str(number_steps))][number_steps] = test_dict.get(number_steps, tens_steps)
			starting_number = jump_number + 1
		if len(str(jump_number + 1)) == len(str(cumalative_steps)) + 1:
			number_steps = int('9' * len(str(cumalative_steps)))
			tens_steps = jump_number + 1 + int('9' * len(str(cumalative_steps))) - cumalative_steps
			test_dict[len(str(number_steps))] = test_dict.get(len(str(number_steps)), {})
			test_dict[len(str(number_steps))][number_steps] = test_dict.get(number_steps, tens_steps)
	return test_dict

def search_number(test_step, test_dict, steps_number_dict):
	test_step_len = len(str(test_step))
	if test_step <= 30:
		print(steps_number_dict[test_step])
	else:
		step_keys = list(test_dict[test_step_len].keys())
		step_values = list(test_dict[test_step_len].values())
		for pos in range(len(step_keys) - 1):
			if step_keys[pos] <= test_step < step_keys[pos + 1]:
				first_digit = int(str(test_dict[test_step_len][step_keys[pos]])[0])
				number = step_values[pos] + (test_step - step_keys[pos]) * first_digit
				if first_digit < 9:
					print(number)
				elif number <= step_values[-2]:
					print(number)
				else:
					print(step_values[-2] - 1)
			if pos == len(step_keys) - 1 - 1 and test_step == step_keys[pos + 1]:
				print(step_values[pos + 1])
steps_number_dict = find_steps_number()
test_dict = create_stepNumber_dict(steps_number_dict)
number_tests = int(input().strip())
for test in range(number_tests):
	step = int(input().strip())
	search_number(step, test_dict, steps_number_dict)


lim = 10 ** 12
fix = [(9, 2), (10, 3)]
pk = 3
p10 = 10
while pk <= lim:
	k = pk
	v = p10
	over = 0
	for ld in range(1, 9):
		step = (p10 - 2 - over) // ld + 1
		v += step * ld + 1
		k += step
		fix.append((v, k))
		over = v % 10
	pf = p10 * 10 - 1
	v = pf
	k = 0
	for ld in reversed(range(2, 10)):
		step = v % p10 // ld + 1
		v -= step * ld
		k += step
	pk += k + v % p10
	fix.append((pf, pk))
	pk += 1
	p10 *= 10
	fix.append((p10, pk))
for ti in range(int(input())):
	k = int(input())
	fx = 0
	while fx < len(fix):
		(v, s) = fix[fx]
		if s == k:
			print(v)
			break
		elif s > k:
			fx -= 1
			(v, s) = fix[fx]
			d = fx % 10
			print(v + d * (k - s))
			break
		fx += 1