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

Let's call a positive integer $M$ a *beautiful number* if the following conditions are satisfied:
The decimal representation of $M$ (without leading zeros) does not contain any zeros.
The sum of squares of all decimal digits of $M$ is a perfect square.

For example, $1$, $4$ and $221$ are beautiful, but $10$ and $333$ are not.

You are given a positive integer $N$. Find the smallest $N$-digit beautiful number or determine that all $N$-digit integers are not beautiful.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $N$.

------  Output ------
For each test case, print a single line containing one integer ― the smallest $N$-digit beautiful number, or $-1$ if there is no such number.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{6}$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (10 points): $1 ≤ N ≤ 100$

Subtask #2 (90 points): $1 ≤ T ≤ 10$

----- Sample Input 1 ------ 
2

1

2
----- Sample Output 1 ------ 
1

34
----- explanation 1 ------ 
Example case 1: It is obvious that $1$ is the smallest beautiful number.

Example case 2: $34$ is beautiful because $3^{2} + 4^{2} = 9 + 16 = 25 = 5^{2}$. On the other hand, we can prove that this is the smallest beautiful number.

Source: codechef | Difficulty: HARD
Tags: Dynamic programming

Mathematics


Solutions:
import sys
import math
import copy

def getInput(num):
	if num:
		inputArr = input().split()
		if len(inputArr) != num:
			print(f'The length is {len(inputArr)} not same as asked for {num}')
			sys.exit(0)
		for i in range(0, len(inputArr)):
			inputArr[i] = int(inputArr[i])
		return inputArr
	elif num == 0:
		return int(input())
	elif num == None:
		inputArr = input().split()
		for i in range(0, len(inputArr)):
			inputArr[i] = int(inputArr[i])
		return inputArr
remArr = [3, 8, 15, 24, 35, 48, 63, 80]
remDict = {}

def isLess(arr0, arr1):
	sum = 0
	tempArr = []
	for i in range(0, 8):
		myVal0 = arr1[i] - arr0[i]
		sum += myVal0
		tempArr.append(myVal0)
	if sum > 0:
		return True
	elif sum < 0:
		return False
	else:
		for i in range(0, 8):
			if tempArr[i] < 0:
				return True
			elif tempArr[i] > 0:
				return False
		else:
			return False

def getRemIndices(tRem):
	if tRem in remDict:
		return copy.deepcopy(remDict[tRem])
	if tRem < 3:
		remDict[tRem] = []
		return []
	indArr = []
	myTempArr = [0, 0, 0, 0, 0, 0, 0, 0]
	for i in range(0, 8):
		if remArr[i] == tRem:
			myTempArr[i] += 1
			return myTempArr
		elif remArr[i] < tRem:
			retArr = getRemIndices(tRem - remArr[i])
			if retArr:
				retArr[i] += 1
			if indArr and retArr:
				if isLess(retArr, indArr):
					indArr = copy.deepcopy(retArr)
			elif retArr:
				indArr = retArr
	remDict[tRem] = copy.deepcopy(indArr)
	return indArr
chrArr = ['2', '3', '4', '5', '6', '7', '8', '9']
for test in range(0, getInput(0)):
	N = getInput(0)
	result = '-1'
	myVal0 = int(math.sqrt(N))
	mySq = myVal0 * myVal0
	if mySq == N:
		result = '1' * N
	else:
		myVal0 += 1
		mySq = myVal0 * myVal0
		myLimit = 80 * N
		myDigitLimit = N
		myResultList = []
		while mySq <= myLimit:
			myRetArr = getRemIndices(mySq - N)
			if myRetArr:
				mySum = 0
				tempResult = ''
				for i in range(0, 8):
					if myRetArr[i]:
						tempResult += chrArr[i] * myRetArr[i]
					mySum += myRetArr[i]
				if myDigitLimit - mySum >= 0:
					myResultList.append(tempResult)
					myLimit = N + 80 * mySum
					myDigitLimit = mySum
			myVal0 += 1
			mySq = myVal0 * myVal0
		resultList = []
		for i in myResultList:
			if len(i) == myDigitLimit:
				resultList.append(i)
		resultList.sort()
		result = resultList[0]
	print('1' * (N - len(result)) + result)


XX = 29
can = [[[False for i in range(XX * 81 + 1)] for j in range(XX)] for k in range(11)]
can[10][0][0] = True
squares = []
i = 1
while i * i <= 10 ** 8:
	squares.append(i * i)
	i += 1
for sm in range(0, XX * 81 + 1):
	for first in range(9, 0, -1):
		for cnt in range(0, XX):
			if cnt == 0:
				can[first][cnt][sm] = sm == 0
			else:
				can[first][cnt][sm] = can[first][cnt][sm] or can[first + 1][cnt][sm]
				t = 0
				while t <= cnt and t * (first * first) <= sm:
					can[first][cnt][sm] = can[first][cnt][sm] or can[first + 1][cnt - t][sm - t * (first * first)]
					t += 1
for _ in range(int(input())):
	n = int(input())
	ans = []
	(cnt, rem, curSum) = (0, n, 0)
	for i in range(1, 10):
		cnt = rem
		while True:
			succ = False
			for x in squares:
				tempSum = curSum + cnt * i * i
				succ = succ or (tempSum <= x and x - tempSum < XX * 81 and can[i + 1][rem - cnt][x - tempSum])
			if succ:
				break
			cnt -= 1
		rem -= cnt
		curSum += cnt * i * i
		while cnt:
			ans.append(i)
			cnt -= 1
	print(*ans, sep='')


(lookup, pre) = ([''] * 2004, ['0', '0'] + [str(i ** 2 - 1) for i in range(2, 10)])
for i in range(2, 10):
	lookup[int(pre[i])] = str(i)
for i in range(3, 2004):
	if lookup[i] != '':
		for j in range(2, 10):
			index = i + int(pre[j])
			if index <= 2003:
				val = ''.join(sorted(lookup[i] + str(j)))
				if lookup[index] == '':
					lookup[index] = val
				else:
					exists = lookup[index]
					if len(val) < len(exists):
						lookup[index] = val
					elif len(val) == len(exists) and val < exists:
						lookup[index] = val

def perfectSquare(num):
	if int(num ** 0.5) ** 2 == num:
		return True
	else:
		return False
for _ in range(int(input())):
	(n, ans) = (int(input()), '')
	if perfectSquare(n):
		print(''.join(['1'] * n))
	else:
		for i in range(1, 2003):
			if perfectSquare(n + i):
				if ans == '':
					ans = lookup[i]
				elif lookup[i] != '':
					if len(lookup[i]) < len(ans):
						ans = lookup[i]
					elif len(lookup[i]) == len(ans):
						if lookup[i] < ans:
							ans = lookup[i]
		if ans == '':
			print(-1)
		else:
			for _ in range(1, n + 1 - len(ans)):
				print(1, end='')
			print(ans)


(vals, temp) = ([], [0] * 8)
for i in range(8):
	temp[i] += 1
	vals.append(tuple(temp))
	temp[i] -= 1
diffs = dict(zip([(i + 2) ** 2 - 1 for i in range(8)], [tuple(val) for val in vals]))
remains = [(i + 2) ** 2 - 1 for i in range(8)]

def gen_smallest_beautiful_num(n):
	if n <= 0:
		return -1
	target = round(n ** 0.5)
	if target ** 2 == n:
		return '1' * n
	max_num = 81 * n
	max_len = n
	tail = None
	while target ** 2 <= max_num:
		cur_tail = compensate(target ** 2 - n, diffs)
		if cur_tail:
			tail = cur_tail if not tail else min(tail, cur_tail, key=int)
			max_len = len(tail)
			max_num = n + 80 * max_len
		target += 1
	return '1' * (n - len(tail)) + tail if tail else '-1'

def less(this: list, that: list):
	if not this:
		return False
	(sum_this, sum_that) = (sum(this), sum(that))
	if sum_this == sum_that:
		return this > that
	elif sum_this < sum_that:
		return True
	else:
		return False

def compensate(diff, diffs):
	r = remains

	def dfs(d):
		if d < 3:
			return
		if d in diffs:
			return list(diffs[d])
		ans = []
		for i in range(8):
			if r[i] > d:
				break
			cur_ans = dfs(d - r[i])
			if cur_ans:
				cur_ans[i] += 1
				if not less(ans, cur_ans):
					ans = cur_ans
		diffs[d] = tuple(ans)
		return ans
	ans = dfs(diff)
	if ans:
		return ''.join((str(i + 2) * d for (i, d) in enumerate(ans)))
try:
	test_num = int(input())
	for _ in range(test_num):
		print(gen_smallest_beautiful_num(int(input())))
except EOFError:
	pass


import math

def main():

	def get_digits(n, k, p, B):
		if n < k * p * p or n > k * 9 * 9:
			return False
		if k == 0:
			return (0,) * (10 - p) if n == 0 else False
		if p == 9:
			return (k,) if n == k * 81 else False
		for K in range(k, B[0] - 1, -1):
			b2 = B[1:] if K == B[0] else (0,) * (9 - p)
			res = get_digits(n - K * p * p, k - K, p + 1, b2)
			if res != False:
				return (K,) + res
		return False
	T = int(input())
	for _ in range(T):
		N = int(input())
		M = math.floor(math.sqrt(N))
		while M * M < N:
			M += 1
		best = (0,) * 9
		while M * M <= 81 * N:
			F = get_digits(M * M, N, 1, best)
			if F:
				best = max(best, F)
			M += 1
		if sum(best) > 0:
			s = ''.join((str(i + 1) * best[i] for i in range(len(best))))
			print(s)
		else:
			print(-1)
main()


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
hashmap = defaultdict(int)
for i in range(1, 9001):
	hashmap[i * i] = 1
memo = defaultdict(lambda : -1)

def recursive(idx, LastDigit, N, List, curSum):
	if memo[curSum, LastDigit, N - idx] == 2:
		return False
	if N == idx:
		if hashmap[curSum] == 1:
			return True
		return False
	for i in range(LastDigit, 10):
		List[idx] = i
		if recursive(idx + 1, i, N, List, curSum + i * i):
			return True
	memo[curSum, LastDigit, N - idx] = 2
	return False
T = int(input().rstrip())
for _ in range(T):
	N = int(input().rstrip())
	List = [0] * N
	if recursive(0, 1, N, List, 0):
		out = ''.join(map(str, List))
		print(out)
	else:
		print(-1)


import math

def isPerSq(number):
	root = math.sqrt(number)
	if int(root) ** 2 == number:
		return True
	else:
		return False

def min_coins(coins, total):
	T = [10 ** 6 + 1 for i in range(total + 1)]
	T[0] = 0
	R = [-1 for i in range(total + 1)]
	for i in range(len(coins)):
		for j in range(1, total + 1):
			if j >= coins[i]:
				if 1 + T[j - coins[i]] <= T[j]:
					T[j] = 1 + T[j - coins[i]]
					R[j] = i
	return (T[-1], R)

def print_coins(R, coins):
	a = []
	start = len(R) - 1
	while start != 0:
		coin = coins[R[start]]
		a.append(int((coin + 1) ** 0.5))
		start = start - coin
	a.sort()
	return a
coins = [i ** 2 - 1 for i in range(2, 10)]
coins.sort(reverse=True)
dp = [10 ** 6 + 1 for i in range(10 ** 6 + 1)]
dp[0] = 0
for i in range(len(coins)):
	for j in range(1, 10 ** 6 + 1):
		if j >= coins[i]:
			if 1 + dp[j - coins[i]] <= dp[j]:
				dp[j] = 1 + dp[j - coins[i]]
T = int(input())
while T:
	N = int(input())
	if isPerSq(N):
		print('1' * N)
	else:
		x = int(N ** 0.5) + 1
		ls = []
		while x ** 2 - N < 10 ** 6 + 1:
			if dp[x ** 2 - N] <= N:
				ls.append([dp[x ** 2 - N], x ** 2 - N])
			x += 1
		ls.sort()
		A = []
		for i in range(len(ls)):
			if i == 0:
				(a, b) = min_coins(coins, ls[i][1])
				A.append(print_coins(b, coins))
			elif ls[i][0] == ls[i - 1][0]:
				(a, b) = min_coins(coins, ls[i][1])
				A.append(print_coins(b, coins))
			else:
				break
		B = []
		for i in range(len(A)):
			B.append(''.join((str(x) for x in A[i])))
		B.sort()
		print('1' * (N - len(B[0])) + B[0])
	T -= 1


import math
ma = 30
dp = [[-1 for i in range(ma + 1)] for j in range(81 * ma + 1)]
for i in range(1, 10):
	dp[i * i][1] = i
for i in range(1, 81 * ma + 1):
	for j in range(2, ma + 1):
		for k in range(1, 10):
			if i - k * k > 0 and dp[i - k * k][j - 1] != -1:
				a = min(dp[i - k * k][j - 1] * 10 + k, k * 10 ** (i - 1) + dp[i - k * k][j - 1])
				dp[i][j] = a if dp[i][j] == -1 else min(a, dp[i][j])
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
		continue
	if int(math.sqrt(n)) ** 2 == n:
		print('1' * n)
		continue
	if int(math.sqrt(81 * n)) == int(math.sqrt(n)):
		print(-1)
		continue
	if n <= ma:
		ans = -1
		(u, d) = (int(math.sqrt(n)), int(math.sqrt(81 * n)) + 1)
		for i in range(u, d):
			if dp[i * i][n] != -1:
				ans = min(dp[i * i][n], ans) if ans != -1 else dp[i * i][n]
		print(ans)
	else:
		ans = -1
		(u, d) = (int(math.sqrt(n)) + 1, int(math.sqrt(81 * n)) + 1)
		one = n
		for i in range(1, ma + 1):
			one -= 1
			for j in range(u, d):
				c = j * j
				if c - one < 81 * ma and dp[c - one][n - one] != -1:
					ans = min(ans, dp[c - one][n - one]) if ans != -1 else dp[c - one][n - one]
			if ans != -1:
				break
		if ans != -1:
			print('1' * one, ans, sep='')
		else:
			print(-1)


import math
from math import floor, ceil, sqrt, log, log10
global_curr_num = [0 for i in range(0, 9)]
pre_ = [0, 1, 34, 122, 1111, 11123, 111112, 1111124, 11111113, 111111111, 1111111114, 11111111126]
last_2 = [11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99]
diff_arr = [0, -1, -1, 2, -1, -1, 22, -1, 3, 222, -1, 23, 2222, -1, 223, 4, 33, 2223, 24, 233, 22223, 224, 2233, 34, 5, 22233, 234, 25, 222233, 2234, 44, 334, 35, 244, 2334, 6, 2244, 22334, 26, 45, 335, 226, 245, 36, 2226, 444, 236, 345, 7, 2236, 46, 27, 22236, 246, 227, 3345, 37, 2227, 346, 56, 4444, 2346, 256, 8, 337, 446, 28, 356, 2446, 228, 66, 38, 57, 266, 238, 257, 2266, 2238, 48, 338, 9, 248, 2338, 29, 2248, 466, 229, 58, 39, 2229, 258, 239, 22229, 448, 566, 49, 77, 2566, 68, 277, 4466, 268, 458, 349, 59, 666, 368, 259, 2666, 2368, 449, 78, 359, 468, 278, 69, 2468, 2278, 269, 378, 577, 2269, 568, 369, 22269, 2568, 88, 3378, 79, 288, 469, 279, 2288, 668, 388, 578, 379, 2388, 2578, 569, 6666, 488, 2569, 89, 777, 4469, 289, 2777, 4668, 2289, 588, 389, 579, 2588, 2389, 2579, 4488, 5668, 489, 778, 99, 688, 2778, 299, 2688, 4588, 2299, 589, 399, 3688, 2589, 2399, 23688, 4489, 788, 499, 779, 2788, 689, 2779, 22788, 2689, 3788, 3499, 599, 5688, 3689, 2599, 25688, 888, 4499, 789, 2888, 4689, 2789, 699, 6688, 3888, 2699, 3789, 5779, 22699, 5689, 3699, 4888, 25689, 889, 7778, 799, 2889, 4699, 2799, 22889, 5888, 3889, 5789, 3799, 23889, 25789, 5699, 56688, 4889, 7788, 899, 6888, 27788, 2899, 26888, 45888, 22899, 5889, 3899, 5799, 25889, 23899, 25799, 44889, 7888, 4899, 7789, 999, 6889, 27789, 2999, 26889, 37888, 22999, 5899, 3999, 36889, 25899, 23999, 8888, 44899, 7889, 4999, 7799, 27889, 6899, 27799, 38888, 26899, 37889, 34999, 5999, 56889, 36899, 25999, 256889, 8889, 44999, 7899, 28889, 46899, 27899, 6999, 58888, 38889, 26999, 37899, 57799, 226999, 56899, 36999, 48889, 77888, 8899, 68888, 7999, 28899, 46999, 27999, 228899, 58889, 38899, 57899, 37999, 238899, 257899, 56999, 78888, 48899, 77889, 8999, 68889, 277889, 28999, 268889, 378888, 228999, 58899, 38999, 57999, 258899, 238999, 88888, 448899, 78889, 48999, 77899, 9999, 68899, 277899, 29999, 268899, 378889, 229999, 58999, 39999, 368899, 258999, 239999, 88889, 448999, 78899, 49999, 77999, 278899, 68999, 277999, 388889, 268999, 378899, 349999, 59999, 568899, 368999, 259999, 778888, 88899, 449999, 78999, 288899, 468999, 278999, 69999, 588889, 388899, 269999, 378999, 577999, 2269999, 568999, 369999, 488899, 778889, 88999, 688889, 79999, 288999, 469999, 279999, 2288999, 588899, 388999, 578999, 379999, 2388999, 888888, 569999, 788889, 488999, 778899, 89999, 688899, 2778899, 289999, 2688899, 3788889, 2289999, 588999, 389999, 579999, 2588999, 2389999, 888889, 4488999, 788899, 489999, 778999, 99999, 688999, 2778999, 299999, 2688999, 3788899, 2299999, 589999, 399999, 3688999, 2589999, 2399999, 888899, 4489999, 788999, 499999, 779999, 2788999, 689999, 2779999, 3888899, 2689999, 3788999, 3499999, 599999, 5688999, 3689999, 2599999, 7788889, 888999, 4499999, 789999, 2888999, 4689999, 2789999, 699999, 5888899, 3888999, 2699999, 3789999, 5779999, 8888888, 5689999, 3699999, 4888999, 7788899, 889999, 6888899, 799999, 2889999, 4699999, 2799999, 22889999, 5888999, 3889999, 5789999, 3799999, 23889999, 8888889, 5699999, 7888899, 4889999, 7788999, 899999, 6888999, 27788999, 2899999, 26888999, 37888899, 22899999, 5889999, 3899999, 5799999, 25889999, 23899999, 8888899, 44889999, 7888999, 4899999, 7789999, 999999, 6889999, 27789999, 2999999, 26889999, 37888999, 22999999, 5899999, 3999999, 36889999, 25899999, 23999999, 8888999, 44899999, 7889999, 4999999, 7799999, 27889999, 6899999, 27799999, 38888999, 26899999, 37889999, 34999999, 5999999, 56889999, 36899999, 25999999, 77888899, 8889999, 44999999, 7899999, 28889999, 46899999, 27899999, 6999999, 58888999, 38889999, 26999999, 37899999, 57799999, 88888889, 56899999, 36999999, 48889999, 77888999, 8899999, 68888999, 7999999, 28899999, 46999999, 27999999, 228899999, 58889999, 38899999, 57899999, 37999999, 238899999, 88888899, 56999999, 78888999, 48899999, 77889999, 8999999, 68889999, 277889999, 28999999, 268889999, 378888999, 228999999, 58899999, 38999999, 57999999, 258899999, 238999999, 88888999, 448899999, 78889999, 48999999, 77899999, 9999999, 68899999, 277899999, 29999999, 268899999, 378889999, 229999999, 58999999, 39999999, 368899999, 258999999, 239999999, 88889999, 448999999, 78899999, 49999999, 77999999, 278899999, 68999999, 277999999, 388889999, 268999999, 378899999, 349999999, 59999999, 568899999, 368999999, 259999999, 778888999, 88899999, 449999999, 78999999, 288899999, 468999999, 278999999, 69999999, 588889999, 388899999, 269999999, 378999999, 577999999, 888888899, 568999999, 369999999, 488899999, 778889999, 88999999, 688889999, 79999999, 288999999, 469999999, 279999999, 2288999999, 588899999, 388999999, 578999999, 379999999, 2388999999, 888888999, 569999999, 788889999, 488999999, 778899999, 89999999, 688899999, 2778899999, 289999999, 2688899999, 3788889999, 2289999999, 588999999, 389999999, 579999999, 2588999999, 2389999999, 888889999, 4488999999, 788899999, 489999999, 778999999, 99999999, 688999999, 2778999999, 299999999, 2688999999, 3788899999, 2299999999, 589999999, 399999999, 3688999999, 2589999999, 2399999999, 888899999, 4489999999, 788999999, 499999999, 779999999, 2788999999, 689999999, 2779999999, 3888899999, 2689999999, 3788999999, 3499999999, 599999999, 5688999999, 3689999999, 2599999999, 7788889999, 888999999, 4499999999, 789999999, 2888999999, 4689999999, 2789999999, 699999999, 5888899999, 3888999999, 2699999999, 3789999999, 5779999999, 8888888999, 5689999999, 3699999999, 4888999999, 7788899999, 889999999, 6888899999, 799999999, 2889999999, 4699999999, 2799999999, 22889999999, 5888999999, 3889999999, 5789999999, 3799999999, 23889999999, 8888889999, 5699999999, 7888899999, 4889999999, 7788999999, 899999999, 6888999999, 27788999999, 2899999999, 26888999999, 37888899999, 22899999999, 5889999999, 3899999999, 5799999999, 25889999999, 23899999999, 8888899999, 44889999999, 7888999999, 4899999999, 7789999999, 999999999, 6889999999, 27789999999, 2999999999, 26889999999, 37888999999, 22999999999, 5899999999, 3999999999, 36889999999, 25899999999, 23999999999, 8888999999, 44899999999, 7889999999, 4999999999, 7799999999, 27889999999, 6899999999, 27799999999, 38888999999, 26899999999, 37889999999, 34999999999, 5999999999, 56889999999, 36899999999, 25999999999, 77888899999, 8889999999, 44999999999, 7899999999, 28889999999, 46899999999, 27899999999, 6999999999, 58888999999, 38889999999, 26999999999, 37899999999, 57799999999, 88888889999, 56899999999, 36999999999, 48889999999, 77888999999, 8899999999, 68888999999, 7999999999, 28899999999, 46999999999, 27999999999, 228899999999, 58889999999, 38899999999, 57899999999, 37999999999, 238899999999, 88888899999, 56999999999, 78888999999, 48899999999, 77889999999, 8999999999, 68889999999, 277889999999, 28999999999, 268889999999, 378888999999, 228999999999, 58899999999, 38999999999, 57999999999, 258899999999, 238999999999, 88888999999, 448899999999, 78889999999, 48999999999, 77899999999, 9999999999, 68899999999, 277899999999, 29999999999, 268899999999, 378889999999, 229999999999, 58999999999, 39999999999, 368899999999, 258999999999, 239999999999, 88889999999, 448999999999, 78899999999, 49999999999, 77999999999, 278899999999, 68999999999, 277999999999, 388889999999, 268999999999, 378899999999, 349999999999, 59999999999, 568899999999, 368999999999, 259999999999, 778888999999, 88899999999, 449999999999, 78999999999, 288899999999, 468999999999, 278999999999, 69999999999, 588889999999, 388899999999, 269999999999, 378999999999, 577999999999, 888888899999, 568999999999, 369999999999, 488899999999, 778889999999, 88999999999, 688889999999, 79999999999, 288999999999, 469999999999, 279999999999, 2288999999999, 588899999999, 388999999999, 578999999999, 379999999999, 2388999999999, 888888999999, 569999999999, 788889999999, 488999999999, 778899999999, 89999999999, 688899999999, 2778899999999, 289999999999, 2688899999999, 3788889999999, 2289999999999, 588999999999, 389999999999, 579999999999, 2588999999999, 2389999999999, 888889999999, 4488999999999, 788899999999, 489999999999, 778999999999, 99999999999, 688999999999, 2778999999999, 299999999999, 2688999999999, 3788899999999, 2299999999999, 589999999999, 399999999999, 3688999999999, 2589999999999, 2399999999999, 888899999999, 4489999999999, 788999999999, 499999999999, 779999999999, 2788999999999, 689999999999, 2779999999999, 3888899999999, 2689999999999, 3788999999999, 3499999999999, 599999999999, 5688999999999, 3689999999999, 2599999999999, 7788889999999, 888999999999, 4499999999999, 789999999999, 2888999999999, 4689999999999, 2789999999999, 699999999999, 5888899999999, 3888999999999, 2699999999999, 3789999999999, 5779999999999, 8888888999999, 5689999999999, 3699999999999, 4888999999999, 7788899999999, 889999999999, 6888899999999, 799999999999, 2889999999999, 4699999999999, 2799999999999, 22889999999999, 5888999999999, 3889999999999, 5789999999999, 3799999999999, 23889999999999, 8888889999999, 5699999999999, 7888899999999, 4889999999999, 7788999999999, 899999999999, 6888999999999, 27788999999999, 2899999999999, 26888999999999, 37888899999999, 22899999999999, 5889999999999, 3899999999999, 5799999999999, 25889999999999, 23899999999999, 8888899999999, 44889999999999, 7888999999999, 4899999999999, 7789999999999, 999999999999, 6889999999999, 27789999999999, 2999999999999, 26889999999999, 37888999999999, 22999999999999, 5899999999999, 3999999999999, 36889999999999, 25899999999999, 23999999999999, 8888999999999, 44899999999999, 7889999999999, 4999999999999, 7799999999999, 27889999999999, 6899999999999, 27799999999999, 38888999999999, 26899999999999, 37889999999999, 34999999999999, 5999999999999, 56889999999999, 36899999999999, 25999999999999, 77888899999999, 8889999999999, 44999999999999, 7899999999999, 28889999999999, 46899999999999, 27899999999999, 6999999999999, 58888999999999, 38889999999999, 26999999999999, 37899999999999, 57799999999999]

def is_sq(a):
	b = int(sqrt(a))
	return (b - 1) * (b - 1) == a or b * b == a or (b + 1) * (b + 1) == a

def pretty_print(a):
	l = 0
	for i in range(0, len(a)):
		for j in range(0, a[i]):
			l += 1
			if l > 0:
				print(i + 1, end='')
	print()

def sum_sq_digits(a):
	ans = 0
	while a > 0:
		ans += a % 10 * (a % 10)
		a = a // 10
	return ans

def smaller_eq_fun(a, b):
	for i in range(0, len(a)):
		if a[i] > b[i]:
			return True
		if a[i] < b[i]:
			return False
	return True

def get_valid_beautiful_num(n, sq):
	if sq < n:
		return False
	if sq == n:
		for i in range(0, 9):
			global_curr_num[i] = 0
		global_curr_num[0] = n
		return True
	ones = n - 2
	nines = 0
	if sq - n > 750:
		tmp = sq - n + 2
		tmp = max(0, tmp // 80 - 5)
		ones = n - 2 - tmp
		nines = tmp
	curr_diff = 0
	for i in range(0, 9):
		global_curr_num[i] = 0
	curr_tmp = [0 for i in range(0, 9)]
	is_possible = False
	for i in range(0, len(last_2)):
		for j in range(0, 9):
			curr_tmp[j] = 0
		curr_diff = sq - (ones + 81 * nines + sum_sq_digits(last_2[i]))
		if curr_diff == 0:
			is_possible = is_possible or True
			curr_tmp[0] = n - nines - 2
			curr_tmp[8] = nines
			curr_tmp[last_2[i] % 10 - 1] += 1
			curr_tmp[last_2[i] // 10 - 1] += 1
			if smaller_eq_fun(curr_tmp, global_curr_num):
				for j in range(0, 9):
					global_curr_num[j] = curr_tmp[j]
		elif curr_diff > 0 and curr_diff < len(diff_arr) and (diff_arr[curr_diff] != -1):
			is_possible = is_possible or True
			curr_tmp[0] = n - nines - 2
			curr_tmp[8] = nines
			curr_tmp[last_2[i] % 10 - 1] += 1
			curr_tmp[last_2[i] // 10 - 1] += 1
			diff_sq = diff_arr[curr_diff]
			while diff_sq > 0:
				curr_tmp[diff_sq % 10 - 1] += 1
				diff_sq = diff_sq // 10
				curr_tmp[0] -= 1
			if smaller_eq_fun(curr_tmp, global_curr_num):
				for j in range(0, 9):
					global_curr_num[j] = curr_tmp[j]
	return is_possible

def get_last_num(a):
	ans = 0
	mul = 1
	for i in range(8, 0, -1):
		for j in range(0, a[i]):
			ans += (i + 1) * mul
			mul *= 10
	return ans
test_c = int(input())
curr_max_las = 0
for t in range(0, test_c):
	n = int(input())
	if n <= 10:
		print(pre_[n])
		continue
	min_sq = ceil(sqrt(n))
	max_sq = floor(sqrt(81 * n)) + 1
	is_possible = False
	curr_num = [0 for i in range(0, 9)]
	for curr_sq in range(min_sq, max_sq):
		flag = get_valid_beautiful_num(n, curr_sq * curr_sq)
		if flag:
			if smaller_eq_fun(global_curr_num, curr_num):
				for i in range(0, len(curr_num)):
					curr_num[i] = global_curr_num[i]
		is_possible = is_possible or flag
	if is_possible:
		pretty_print(curr_num)
	else:
		while True:
			gsgs = 1
		print(-1)


import math
store = {}

def beautiful_number(M, N, min_is, s):
	args = (M, N, min_is, s)
	if args in store:
		return store[args]
	if M < N or M - N * 81 > 0:
		return None
	if s == 9:
		mi = M - N * s * s
		res = [N] if mi == 0 else None
		store[args] = res
		return res
	max_i = min(N, int((M - 81 * N) / (s * s - 81)))
	min_i = min_is
	for i in range(max_i, min_i - 1, -1):
		mi = M - i * s * s
		res = beautiful_number(mi, N - i, 0, s + 1)
		if res is not None:
			res = [i] + res
			store[args] = res
			return res
	store[args] = None
	return None
l2a = lambda a: ''.join([str(i + 1) * x for (i, x) in enumerate(a)]) if a is not None else -1
squares_list = [n * n for n in range(1, math.floor(math.sqrt(81 * 1000000)) + 1)]

def min_beautiful_number(N):
	beautiful_numbers = []
	min_is = 0
	for M in squares_list:
		if M >= N + 81 or M == N:
			if M <= 81 * N:
				a = beautiful_number(M, N, min_is, 1)
				if a is not None:
					min_is = a[0]
					break
	for M in squares_list:
		if M >= N:
			if M <= 81 * N:
				a = beautiful_number(M, N, min_is, 1)
				if a is not None:
					if min_is <= a[0]:
						b = l2a(a)
						beautiful_numbers.append(b)
						min_is = a[0]
			else:
				break
	return min(beautiful_numbers) if beautiful_numbers else -1
T = int(input())
for _ in range(T):
	N = int(input())
	print(min_beautiful_number(N))


import sys, math
sys.setrecursionlimit(10 ** 6)

def rec3(digit, carry=0, st='', t=1):
	ins1 = math.floor(carry ** 0.5)
	ins2 = (ins1 + 1) ** 2
	ins3 = carry + digit * 9 ** 2
	if ins2 > ins3:
		return False
	if digit <= 0:
		if float(carry ** 0.5).is_integer():
			return st
		else:
			return False
	elif digit == 1:
		y = [i for i in range(t, 10) if float((carry + i ** 2) ** 0.5).is_integer()]
		if len(y) != 0:
			return st + str(y[0])
		else:
			return False
	for i in range(t, 10):
		tst = st + str(i)
		x = rec3(digit - 1, carry + i ** 2, tst, i)
		if x != False:
			return x
	return False

def generator(n):
	if float(n ** 0.5).is_integer():
		return '1' * n
	for i in range(n - 1, -1, -1):
		x = rec3(n - i, i)
		if x != False:
			return '1' * i + x
	return -1
for _ in range(int(input())):
	n = int(input())
	print(generator(n))


import math
poss = [None]
poss.append({3: '2', 8: '3', 15: '4', 24: '5', 35: '6', 48: '7', 63: '8', 80: '9'})

def digitSum(n):
	r = 0
	while n:
		(r, n) = (r + (n % 10) ** 2, n // 10)
	return r

def isPerfectSquare(n):
	return math.sqrt(n) - math.floor(math.sqrt(n)) == 0

def isBeautifulNumber(n):
	digit_sum = digitSum(n)
	if isPerfectSquare(digit_sum):
		return True
	return False

def squares(a, b):
	start = math.ceil(math.sqrt(a))
	end = math.floor(math.sqrt(b))
	for num in range(start, end + 1):
		yield (num ** 2)
for i in range(2, 40):
	poss.append({})
	for (key, value) in poss[i - 1].items():
		for (base, orig_value) in poss[1].items():
			new_key = key + base
			new_value = ''.join(sorted(value + orig_value))
			if new_key not in poss[i]:
				poss[i][new_key] = new_value
			elif new_value < poss[i][new_key]:
				poss[i][new_key] = new_value
t = int(input())
for test in range(t):
	digs = int(input())
	found = False
	n = digs
	max_change = 81 * n
	for i in range(1, digs + 1):
		min_ans = '9' * digs
		for square in squares(n, max_change):
			diff = square - n
			if diff > i * 80:
				break
			if diff == 0:
				found = True
				ans = '1' * digs
				min_ans = min(min_ans, ans)
			if diff in poss[i]:
				found = True
				ans = '1' * (digs - len(poss[i][diff])) + poss[i][diff]
				min_ans = min(min_ans, ans)
		if found:
			print(min_ans)
			break


import itertools
import math
arr = []
dic = {}

def isSquare(n):
	return math.sqrt(n) == int(math.sqrt(n))
for i in range(8):
	arr = arr + list(itertools.product([3, 8, 15, 24, 35, 48, 63, 80], repeat=i))
for i in arr:
	s = sum(i)
	if s not in dic:
		dic[s] = i
arr = []
keys = [dic[i] for i in dic]
for i in range(3):
	arr = arr + list(itertools.product(keys, repeat=i))
for i in arr:
	s = ()
	try:
		s = s + i[0]
		s = s + i[1]
	except:
		pass
	if sum(s) not in dic:
		dic[sum(s)] = s
arr = []
keys = [dic[i] for i in dic]
for i in range(3):
	arr = arr + list(itertools.product(keys, repeat=i))
for i in arr:
	s = ()
	try:
		s = s + i[0]
		s = s + i[1]
	except:
		pass
	if sum(s) not in dic:
		dic[sum(s)] = s

def f(N):
	res = []
	for i in dic:
		if isSquare(i + N):
			digits = dic[i]
			break
	digits = list(digits)
	digits.sort()
	s = ''
	for i in range(N - len(digits)):
		s += '1'
	for i in digits:
		s += str(int(math.sqrt(i + 1)))
	return s
T = int(input())
for i in range(T):
	N = int(input())
	print(f(N))


import sys
sys.setrecursionlimit(10 ** 8)

def is_sq(num):
	sqrt = int(num ** 0.5)
	return sqrt ** 2 == num

def force(n):
	res = [None] * n
	dp = {}

	def recurse(cur, acu):
		if (cur, acu) in dp:
			return dp[cur, acu]
		if cur == n:
			if is_sq(acu):
				return True
			return False
		for i in range(1, 10):
			if recurse(cur + 1, acu + i * i):
				dp[cur, acu] = True
				res[cur] = i
				return True
		dp[cur, acu] = False
		return False
	recurse(0, 0)
	print(*res, sep='')
for i in range(int(input())):
	force(int(input()))


import math

def isPerfectSquare(x):
	sr = math.sqrt(x)
	return sr - math.floor(sr) == 0
T = int(input())
for jok in range(T):
	n = int(input())
	ans = -1
	lown = 0
	upn = 0
	nn = n
	full = 0
	ful = 0
	fu = 0
	if isPerfectSquare(n):
		print('1' * n)
		continue
	if n == 2:
		print(34)
		continue
	elif n == 3:
		print(122)
		continue
	elif n == 5:
		print(11123)
		continue
	elif n == 6:
		print(111112)
		continue
	elif n == 7:
		print(1111124)
		continue
	elif n == 8:
		print(11111113)
		continue
	elif n == 10:
		print(1111111114)
		continue
	elif n == 11:
		print(11111111126)
		continue
	elif n == 12:
		print(111111111115)
		continue
	elif n == 13:
		print(1111111111112)
		continue
	elif n == 14:
		print(11111111111116)
		continue
	elif n == 15:
		print(111111111111128)
		continue
	elif n == 17:
		print(11111111111111113)
		continue
	elif n == 18:
		print(111111111111111118)
		continue
	elif n == 19:
		print(1111111111111111122)
		continue
	elif n == 20:
		print(11111111111111111119)
		continue
	elif n == 21:
		print(111111111111111111114)
		continue
	elif n == 22:
		print(1111111111111111111112)
		continue
	elif n == 23:
		print(11111111111111111111168)
		continue
	elif n == 24:
		print(111111111111111111111335)
		continue
	cc = upn
	flag = 0
	i = 2
	puc = n
	ans = -1
	numm = 0
	i1 = i2 = i3 = i4 = i5 = i6 = i7 = i8 = i9 = 0
	for i1 in range(n, -1, -1):
		bye = n - i1
		if bye == 19:
			break
		for i2 in range(n - i1, -1, -1):
			for i3 in range(n - i1 - i2, -1, -1):
				for i4 in range(n - i1 - i2 - i3, -1, -1):
					for i5 in range(n - i1 - i2 - i3 - i4, -1, -1):
						for i6 in range(n - i1 - i2 - i3 - i4 - i5, -1, -1):
							for i7 in range(n - i1 - i2 - i3 - i4 - i5 - i6, -1, -1):
								for i8 in range(n - i1 - i2 - i3 - i4 - i5 - i6 - i7, -1, -1):
									for i9 in range(n - i1 - i2 - i3 - i4 - i5 - i6 - i7 - i8, -1, -1):
										if i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 != n:
											continue
										xx = 1 * i1 + 4 * i2 + 9 * i3 + 16 * i4 + 25 * i5 + 36 * i6 + 49 * i7 + 64 * i8 + 81 * i9
										if isPerfectSquare(xx):
											flag = 1
											break
									if flag == 1:
										break
								if flag == 1:
									break
							if flag == 1:
								break
						if flag == 1:
							break
					if flag == 1:
						break
				if flag == 1:
					break
			if flag == 1:
				break
		if flag == 1:
			break
	if flag == 0:
		i1 = i2 = i3 = i4 = i5 = i6 = i7 = i8 = i9 = 0
		nine = 20
		n = n - 20
		for i1 in range(n, -1, -1):
			for i2 in range(n - i1, -1, -1):
				for i3 in range(n - i1 - i2, -1, -1):
					for i4 in range(n - i1 - i2 - i3, -1, -1):
						for i5 in range(n - i1 - i2 - i3 - i4, -1, -1):
							for i6 in range(n - i1 - i2 - i3 - i4 - i5, -1, -1):
								for i7 in range(n - i1 - i2 - i3 - i4 - i5 - i6, -1, -1):
									for i8 in range(n - i1 - i2 - i3 - i4 - i5 - i6 - i7, -1, -1):
										for i9 in range(n - i1 - i2 - i3 - i4 - i5 - i6 - i7 - i8, -1, -1):
											if i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 != n:
												continue
											xx = 1 * i1 + 4 * i2 + 9 * i3 + 16 * i4 + 25 * i5 + 36 * i6 + 49 * i7 + 64 * i8 + 81 * (i9 + nine)
											if isPerfectSquare(xx):
												flag = 1
												break
										if flag == 1:
											break
									if flag == 1:
										break
								if flag == 1:
									break
							if flag == 1:
								break
						if flag == 1:
							break
					if flag == 1:
						break
				if flag == 1:
					break
			if flag == 1:
				i9 = i9 + nine
				break
	if flag == 0:
		print(-1)
	else:
		print('1' * i1, end='')
		print('2' * i2, end='')
		print('3' * i3, end='')
		print('4' * i4, end='')
		print('5' * i5, end='')
		print('6' * i6, end='')
		print('7' * i7, end='')
		print('8' * i8, end='')
		print('9' * i9, end='')
		print()


V = [3, 8, 15, 24, 35, 48, 63, 80]

def min_change(C):
	(table, solution) = min_change_table(C)
	(num_coins, coins) = (table[-1], [])
	if num_coins == float('inf'):
		return []
	while C > 0:
		coins.append(V[solution[C]])
		C -= V[solution[C]]
	return coins

def min_change_table(C):
	(m, n) = (C + 1, 8)
	(table, solution) = ([0] * m, [0] * m)
	for i in range(1, m):
		(minNum, minIdx) = (float('inf'), -1)
		for j in range(n):
			if V[j] <= i and 1 + table[i - V[j]] < minNum:
				minNum = 1 + table[i - V[j]]
				minIdx = j
		table[i] = minNum
		solution[i] = minIdx
	return (table, solution)
import math
s = math.sqrt
f = math.floor
t = int(input())
ans = list()
for _ in range(t):
	n = int(input())
	a = s(n)
	b = f(a)
	if a - b == 0:
		ans.append('1' * n)
	else:
		m = list()
		l = len
		for i in range(b + 1, b + 11):
			x = min_change(i ** 2 - n)
			if x:
				m.append(x)
		m.sort(key=lambda x: (l(x), x))
		m[0].sort()
		temp = ''
		for i in m[0]:
			temp += str(int(s(i + 1)))
			n -= 1
		temp = '1' * n + temp
		ans.append(temp)
for x in ans:
	print(x)


import math as m1
import sys
sys.setrecursionlimit(10 ** 5)

def count(S, m, n, res, co):
	res.append(S[m - 1])
	if n == 0:
		if len(res) == co + 1:
			fre.append(res)
		return 1
	if n < 0 or len(res) - 1 >= co:
		return 0
	if m <= 0 and n >= 1:
		return 0
	return count(S, m - 1, n, res[:-1], co) + count(S, m, n - S[m - 1], res[:], co)
arr = [4, 9, 16, 25, 36, 49, 64, 81]
arr2 = [1, 4, 9, 16, 25, 36, 49, 64, 81]
m = len(arr)
t = int(input())
while t:
	t -= 1
	res = []
	fre = []
	flag = 0
	f = int(input())
	z = m1.ceil(pow(f, 0.5))
	if m1.ceil(pow(f, 0.5)) == m1.floor(pow(f, 0.5)):
		print('1' * f)
		continue
	c = 0
	while c != 17:
		c += 1
		if c >= 10:
			for i in range(z, z + 2):
				te = i * i - f + c
				count(arr, m, te, [], c)
				if len(fre) != 0:
					flag = 1
					break
		else:
			for i in range(z, z + 7):
				te = i * i - f + c
				count(arr, m, te, [], c)
				if len(fre) != 0:
					flag = 1
		if flag == 1:
			break
	if flag == 0:
		c = 6
		while c != 15:
			c += 1
			for i in range(z, z + 2):
				te = i * i - (f - c - c) - 81 * c
				count(arr2, 9, te, [], c)
				if len(fre) != 0:
					flag = 1
			if flag == 1:
				break
		for i in fre:
			i.sort()
		fre.sort()
		print('1' * (f - (c - 1 + len(fre[0]))), end='')
		for i in fre[0][1:]:
			print(str(int(pow(i, 0.5))), end='')
		print('9' * c)
		continue
	for i in fre:
		i.sort()
	fre.sort()
	print('1' * (f - c), end='')
	s1 = ''
	for i in fre[0][1:]:
		print(str(int(pow(i, 0.5))), end='')
	print()


from itertools import combinations_with_replacement
import math
m = {i * i - 1: [i * i - 1] for i in range(2, 10)}
for _ in range(50):
	for (kk, v) in list(m.items()):
		for i in [3, 8, 15, 24, 35, 48, 63, 80]:
			if i <= v[0]:
				key = kk + i
				if key not in m or len(v) + 1 < len(m[key]) or ([i] + v < m[key] and len(v) + 1 == len(m[key])):
					m[key] = [i] + v
b = {n * n - 1: str(n) for n in range(2, 10)}
T = int(input())
for _ in range(0, T):
	N = int(input())
	if N == 2:
		print('34')
	else:
		best = -1
		u = math.ceil(math.sqrt(N))
		if u * u == N:
			print(N * '1')
			continue
		u2 = 9 * u
		while u < u2:
			t = u * u - N
			if t in m:
				s = ''.join((b[v] for v in m[t]))
				if int(s) < int(best) or best == -1:
					best = s
			u += 1
		if best == -1:
			print('-1')
		else:
			print((N - len(best)) * '1' + best)


def binarySearch(arr, l, r, x):
	if r >= l:
		mid = int(l + (r - l) / 2)
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binarySearch(arr, l, mid - 1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	else:
		return -1
from itertools import combinations_with_replacement
x = list(combinations_with_replacement([1, 4, 9, 16, 25, 36, 49, 64, 81], 15))
x.sort(key=lambda p: sum(p))
totals = list(map(sum, x))
my_squares = [int(x ** 2) for x in range(1, 9001)]
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(34)
	elif n == 1:
		print(1)
	elif n == 3:
		print(122)
	elif n == 4:
		print(1111)
	elif n == 5:
		print(11123)
	elif n == 6:
		print(111112)
	elif n == 7:
		print(1111124)
	elif n == 8:
		print(11111113)
	elif n == 9:
		print(111111111)
	elif n == 10:
		print(1111111114)
	elif n == 11:
		print(11111111126)
	elif n == 12:
		print(111111111115)
	elif n == 13:
		print(1111111111112)
	elif n == 14:
		print(11111111111116)
	elif n == 15:
		print(111111111111128)
	elif n == 16:
		print(1111111111111111)
	elif n == 17:
		print(11111111111111113)
	elif n == 18:
		print(111111111111111118)
	elif n == 19:
		print(1111111111111111122)
	elif n == 20:
		print(11111111111111111119)
	elif n == 21:
		print(111111111111111111114)
	elif n == 22:
		print(1111111111111111111112)
	elif n == 23:
		print(11111111111111111111168)
	elif n == 24:
		print(111111111111111111111335)
	else:
		my_arr = []
		count = 0
		while len(my_arr) == 0:
			for square in my_squares:
				b = binarySearch(totals, 0, len(totals) - 1, square + 15 - n + count - 81 * count)
				if b != -1:
					l = b
					while l < len(totals) and totals[b] == totals[l]:
						my_arr.append(x[l])
						l += 1
					l = b
					while l >= 0 and totals[b] == totals[l]:
						my_arr.append(x[l])
						l -= 1
			count += 1
		my_term = min(my_arr)
		to_add = [int(x ** 0.5) for x in my_term]
		for i in range(n - 15 - count + 1):
			print(1, end='')
		for term in to_add:
			print(term, end='')
		for i in range(count - 1):
			print(9, end='')
		print('')


t = int(input())
from math import sqrt
sqs = set([i * i for i in range(10000)])

def haszero(n):
	while n:
		if n % 10 < 2:
			return True
		n //= 10
sqm1 = [i * i - 1 for i in range(10)]
how_many = [None] * 10000
how_many[0] = [0, 1]
for i in range(10000):
	if how_many[i] is not None:
		for j in range(how_many[i][1] % 10, 10):
			nxt = i + j * j - 1
			if nxt >= 10000:
				break
			nv = [how_many[i][0] + 1, how_many[i][1] * 10 + j]
			if how_many[nxt] is None or nv[1] <= how_many[nxt][1]:
				how_many[nxt] = nv
for numtest in range(1, t + 1):
	n = int(input())
	z = int(sqrt(n + 0.5))
	zz = z
	zzz = None
	while z < zz + 100:
		if z * z >= n and z * z < n + 10000 and (how_many[z * z - n] is not None) and (how_many[z * z - n][0] <= n):
			if zzz is None or zzz > how_many[z * z - n]:
				zzz = how_many[z * z - n]
		z += 1
	print('1' * (n - zzz[0]) + str(zzz[1])[1:])


import math
from itertools import combinations_with_replacement

def find_SBN():
	if N in sqSet:
		return '1' * N
	ctr = N
	while ctr >= 0:
		for num in combinations_with_replacement([4, 9, 16, 25, 36, 49, 64, 81], N - ctr):
			s = ctr + sum(num)
			if s in sqSet:
				return '1' * ctr + ''.join([str(int(math.sqrt(_))) for _ in num])
		ctr -= 1
	return '-1'
T = int(input())
opList = []
sqSet = {i * i for i in range(9001)}
for x in range(T):
	N = int(input())
	opList.append(find_SBN())
print('\n'.join(opList))


nums = [0, 3, 8, 15, 24, 35, 48, 63, 80]
extras = [[]]
curr = 1
while curr < 4500:
	poss = []
	p = 100
	for x in range(2, 10):
		t = curr + 1 - x * x
		if t >= 0:
			if extras[t] != -1:
				a = extras[t].copy()
				a.append(x - 1)
				if len(a) == p:
					a.sort()
					if a < poss:
						poss = a
				elif len(a) < p:
					p = len(a)
					poss = a
					poss.sort()
	if poss == []:
		extras.append(-1)
	else:
		extras.append(poss)
	curr += 1

def minroot(n):
	a = int(n ** 0.5)
	if a ** 2 == n:
		return a
	return a + 1

def ltoi(lis):
	res = 0
	for x in lis:
		res *= 10
		res += x
	return res

def beauty(n):
	m = minroot(n)
	t = -1
	while m ** 2 - n < 4000:
		if extras[m ** 2 - n] == -1:
			m += 1
		else:
			if t == -1:
				t = ltoi(extras[m ** 2 - n])
			elif ltoi(extras[m ** 2 - n]) < t:
				t = ltoi(extras[m ** 2 - n])
			m += 1
	z = str(t)
	l = len(z)
	y = str(int('1' * l) + t)
	b = '1' * (n - l) + y
	return b
t = int(input())
for x in range(t):
	n = int(input())
	print(beauty(n))