Sherlock Holmes suspects his archenemy Professor Moriarty is once again plotting something diabolical. Sherlock's companion, Dr. Watson, suggests Moriarty may be responsible for MI6's recent issues with their supercomputer, The Beast. 

Shortly after resolving to investigate, Sherlock receives a note from Moriarty boasting about infecting The Beast with a virus.  He also gives him a clue:  an integer. Sherlock determines the key to removing the virus is to find the largest Decent Number having that number of digits.

A Decent Number has the following properties:

Its digits can only be 3's and/or 5's.
The number of 3's it contains is divisible by 5.
The number of 5's it contains is divisible by 3.
It is the largest such number for its length. 

Moriarty's virus shows a clock counting down to The Beast's destruction, and time is running out fast. Your task is to help Sherlock find the key before The Beast is destroyed!

For example, the numbers $55533333$ and $555555$ are both decent numbers because there are $3$ $5$'s and $5$ $3$'s in the first, and $6$ $5$'s in the second.  They are the largest values for those length numbers that have proper divisibility of digit occurrences.  

Function Description

Complete the decentNumber function in the editor below.     

decentNumber has the following parameter(s):  

int n: the length of the decent number to create  

Prints  

Print the decent number for the given length, or $-1$ if a decent number of that length cannot be formed. No return value is expected.  

Input Format

The first line is an integer, $t$, the number of test cases. 

The next $t$ lines each contain an integer $n$, the number of digits in the number to create.

Constraints

$1\leq t\leq20$ 

$1\leq n\leq10000$  

Sample Input
STDIN   Function
-----   --------
4       t = 4
1       n = 1 (first test case)
3       n = 3 (second test case)
5
11

Sample Output
-1
555
33333
55555533333

Explanation

For $n=1$, there is no Decent Number having $1$ digit, so print $-1$. 

For $n=3$, $555$ is the only possible number. (Decent Number Property 3). 

For $n=5$, $33333$ is the only possible number. (Decent Number Property 2). 

For $n=11$, $55555533333$ is the Decent Number.  All other permutations of these digits are not decent (Decent Number Property 4).

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

Starter code:

Solutions:
T = int(input())
for i in range(T):
	k = int(input())
	n5 = k
	n3 = 0
	done = False
	while n5 >= 0:
		if n5 % 3 == 0 and n3 % 5 == 0:
			for j in range(n5):
				print('5', end='')
			for j in range(n3):
				print('3', end='')
			print()
			done = True
			break
		n5 -= 1
		n3 += 1
	if not done:
		print(-1)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N < 3:
		print(-1)
	else:
		k = N - N % 3
		if k < N:
			while k > 0 and (N - k) % 5 > 0:
				k -= 3
		if (N - k) % 5 == 0:
			print('5' * k + '3' * (N - k))
		else:
			print(-1)


def divisible(numerator, denominator):
	return numerator % denominator == 0

def valid(five_count, three_count):
	return divisible(five_count, 3) and divisible(three_count, 5)

def not_solved(five_count, three_count):
	return five_count > -1 and (not valid(five_count, three_count))

def build_str(five_count, three_count):
	digits = ['5' for x in range(0, five_count)] + ['3' for x in range(0, three_count)]
	return ''.join(digits)
test_cases = int(input())
for i in range(0, test_cases):
	digits = int(input())
	five_count = digits
	three_count = 0
	while not_solved(five_count, three_count):
		five_count -= 1
		three_count += 1
	print(build_str(five_count, three_count) if valid(five_count, three_count) else -1)


def SOLVE():
	x = int(input())
	t = x // 3
	while t >= 0:
		if (x - t * 3) % 5 == 0:
			print('5' * t * 3, end='')
			print('3' * (x - t * 3))
			return
		t -= 1
	print(-1)
	return
t = int(input())
while t > 0:
	t -= 1
	SOLVE()


def largest_decent_number(length):
	if length < 3 or length in (4, 7):
		return -1
	else:
		num_threes = 0
		while (length - num_threes) % 3 != 0:
			num_threes += 5
		return '5' * (length - num_threes) + '3' * num_threes
T = int(input())
for i in range(T):
	print(largest_decent_number(int(input())))


num = input()
num = int(num)
nums = []
for i in range(0, num):
	nums.append(input())
for i in range(0, len(nums)):
	(num5, num3) = (int(nums[i]), 0)
	while num5 > 0:
		if num5 % 3 == 0 and num3 % 5 == 0:
			break
		else:
			num5 -= 1
			num3 += 1
	if num5 % 3 == 0 and num3 % 5 == 0:
		result = [5 for i in range(num5)]
		result.extend([3 for i in range(num3)])
		print(*result, sep='')
	else:
		print('-1')


T = int(input())
for i in range(T):
	n = int(input())
	fx = 0
	tx = n // 3
	flag = True
	while fx * 5 + tx * 3 != n:
		for i in range(tx, -1, -1):
			if fx * 5 + i * 3 == n:
				tx = i
				flag = False
				break
		if flag == False:
			break
		fx += 1
		if fx > n // 5:
			print(-1)
			fx = tx = 0
			break
	c = []
	c = ['5' * (tx * 3) + '3' * (fx * 5)]
	if fx != 0 or tx != 0:
		print(int(c[0]))


t = int(input())

def solve(n):
	n_3 = 0
	found = 0
	while n_3 <= n:
		if (n - n_3) % 3 == 0:
			found = 1
			break
		else:
			n_3 += 5
	str = ''
	if found == 0:
		print(-1)
	else:
		for i in range(n - n_3):
			print(5, end='')
		for i in range(n_3):
			print(3, end='')
		print(' ')
for i in range(t):
	n = int(input())
	solve(n)


import math

def func():
	T = int(input())
	for i in range(T):
		N = int(input())
		if N < 3:
			print('-1')
			continue
		if N % 3 == 0:
			str = ''
			str += '5' * N
			print(str)
			continue
		c5 = math.floor(N / 3.0) * 3
		c3 = 0
		x = True
		while x == True:
			c3 = N - c5
			if c3 % 5 == 0:
				str = ''
				str += '5' * c5
				str += '3' * c3
				print(str)
				x = False
				break
			else:
				c5 -= 3
			if c5 <= 0:
				c5 = 0
				if N % 5 == 0:
					str = ''
					str += '3' * N
					print(str)
					x = False
					break
				else:
					print('-1')
					x = False
					break
func()


def getNumString(n):
	numoffive = n
	numofthree = n - numoffive
	while numoffive >= 0 and numofthree >= 0:
		if numoffive % 3 == 0 and numofthree % 5 == 0:
			return '5' * numoffive + '3' * numofthree
		else:
			numoffive -= 1
			numofthree = n - numoffive
	if numoffive < 0 or numofthree < 0:
		return ''
	return ''
t = int(input())
for i in range(0, t):
	n = int(input())
	st = getNumString(n)
	if st == '':
		print('-1')
	else:
		print(st)


notest = int(input())
tl = []
for c in range(notest):
	tl.append(int(input()))
for c in tl:
	fc = c
	tc = 0
	for x in range(fc + 1):
		if fc % 3 == 0 and tc % 5 == 0:
			break
		else:
			fc -= 1
			tc += 1
	else:
		print('-1')
		continue
	print(fc * '5' + tc * '3')


import sys

def isValidDigit(number):
	div3 = number // 3
	mod3 = number % 3
	if mod3 == 0:
		return (0, number)
	if number < 5:
		return (0, 0)
	temp = number
	count3 = 0
	for i in range(2):
		temp -= 5
		count3 += 5
		if temp % 3 == 0 and temp >= 0:
			return (count3, number - count3)
	return (0, 0)

def proc(number):
	(num3, num5) = isValidDigit(number)
	if num3 == 0 and num5 == 0:
		return '-1'
	temp = '5' * num5 + '3' * num3
	return temp

def main():
	num = int(sys.stdin.readline())
	for i in range(num):
		ret = proc(int(sys.stdin.readline()))
		print(ret)
main()


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

def check_num(k):
	(fives, threes) = (k, 0)
	while threes <= k:
		if fives % 3 == 0 and threes % 5 == 0:
			return (fives, threes)
		else:
			fives -= 5
			threes += 5
for i in range(t):
	k = int(sys.stdin.readline())
	if check_num(k):
		(fives, threes) = check_num(k)
		print('5' * fives + '3' * threes)
	else:
		print(-1)


def iterative_repeat_subtract(n, sequence):
	stacklist = []
	doublestack = False
	flag = True
	result = True
	n1 = n
	seq1 = list(sequence)
	while flag:
		if n1 < 3 and n1 > 0 and (len(stacklist) == 0):
			result = False
			break
		elif n1 < 0 and len(stacklist) == 0:
			result = False
			print('We are here')
			break
		elif n1 == 0 and len(stacklist) == 0:
			result = False
			break
		elif n1 < 3 and n1 > 0:
			result = False
		elif n1 < 0:
			result = False
		elif n1 == 0:
			result = True
			break
		if result:
			n1 -= 3
			stacklist.append(3)
			seq1.append('555')
			result = True
			continue
		else:
			value = stacklist.pop()
			seq1.pop()
			if value == 3:
				n1 += 3
				n1 -= 5
				stacklist.append(5)
				seq1.append('33333')
				result = True
				continue
			elif value == 5:
				n1 += 5
				if n1 == n:
					result = False
					break
				result = False
				continue
	return (result, seq1)

def iterative_repeat_subtract1(n, sequence):
	old_seq = []
	new_seq = []
	sub_seq = []
	passed_in_seq = []
	final_seq = []
	new_n = n
	passed_in_n = n
	prev_sub = 0
	result = True
	flag = True
	passed_in_seq = list(sequence)
	exec_three = True
	exec_five = False
	while flag:
		if passed_in_n < 3 and passed_in_n > 0:
			final_seq = list(passed_in_seq)
			result = False
		elif passed_in_n < 0:
			final_seq = list(passed_in_seq)
			result = False
		elif passed_in_n == 0 and len(passed_in_seq) == 0:
			final_seq = list(passed_in_seq)
			result = False
		elif passed_in_n == 0:
			result = True
			final_seq = list(passed_in_seq)
			break
		else:
			result = True
		if result:
			if exec_three:
				passed_in_n = passed_in_n - 3
				new_seq = list(passed_in_seq)
				new_seq.append('555')
				sub_seq.append(3)
				exec_three = True
				continue
		elif exec_three:
			exec_three = False
			exec_five = True
			result = True
			passed_in_seq.pop()
			sub_seq.pop()
			passed_in_n += 3
		if result:
			if exec_five:
				new_n = passed_in_n - 5

def repeat_subtract(n, sequence):
	new_n = n
	if new_n < 3 and new_n > 0:
		return (False, sequence)
	elif new_n < 0:
		return (False, sequence)
	elif new_n == 0 and len(sequence) == 0:
		return (False, sequence)
	elif new_n == 0:
		return (True, sequence)
	new_n = n - 3
	new_sequence = list(sequence)
	new_sequence.append('555')
	(result, res_sequence) = repeat_subtract(new_n, new_sequence)
	if result:
		new_sequence = res_sequence
		return (True, new_sequence)
	new_n = n - 5
	new_sequence = list(sequence)
	new_sequence.append('33333')
	(result, res_sequence) = repeat_subtract(new_n, new_sequence)
	if result:
		new_sequence = res_sequence
		return (True, new_sequence)
	new_sequence = sequence
	return (False, new_sequence)

def sherlock_main(n):
	sequence = []
	(result, sequence) = iterative_repeat_subtract(n, sequence)
	if result:
		return ''.join(sequence)
	else:
		return -1

def test_sherlock():
	for n in range(10000):
		print('\n\n')
		print(sherlock_main(n))

def input_sherlock():
	T = int(input())
	n = []
	for i in range(T):
		n.append(int(input()))
	for number in n:
		print(sherlock_main(number))
input_sherlock()


import sys
t = int(sys.stdin.readline())
numbers = sys.stdin.readlines()
for i in numbers:
	for n in range(0, 3):
		bla = int(i) - n * 5
		if bla < 0:
			print(-1)
			break
		if bla % 3 != 0:
			continue
		else:
			decent = '5' * bla + '3' * (n * 5)
			print(decent)
			break


t = int(input())
for i in range(t):
	n = int(input())
	t = 0
	if n % 3 == 0:
		f = n
		t = 0
	elif n % 3 == 1:
		t = 10
		f = n - 10
	elif n % 3 == 2:
		t = 5
		f = n - 5
	if n < t:
		print('-1')
	else:
		print('5' * f + '3' * t)


T = int(input())
for test in range(T):
	N = int(input())
	if N in (1, 2, 4, 7):
		print(-1)
	elif N % 3 == 0:
		print(''.join([str(5) for _ in range(N)]))
	else:
		rem = N % 3
		if rem == 1:
			three = '3333333333'
		else:
			three = '33333'
		fives = int(N - len(three))
		print(''.join([str(5) for _ in range(fives)]) + three)


def calc(n):
	if n % 3 == 0:
		return '5' * n
	if n < 5:
		return '-1'
	for x in range(1, n // 5 + 1):
		m = x * 5
		y = (n - m) // 3
		if m + y * 3 == n:
			return '5' * y * 3 + '3' * x * 5
	return '-1'

def main():
	t = int(input().strip())
	for i in range(t):
		n = int(input().strip())
		print(calc(n))
main()


def digits(k):
	x = k
	y = 0
	while not (x % 3 == 0 and y % 5 == 0):
		x -= 1
		y += 1
		if x < 0:
			return (0, 0)
	return (x, y)

def main():
	test_case_c = int(input())
	while test_case_c:
		test_case_c -= 1
		k = int(input())
		(digits5, digits3) = digits(k)
		if (digits5, digits3) == (0, 0):
			print(-1)
		else:
			for _ in range(digits5):
				print('5', end='')
			for _ in range(digits3):
				print('3', end='')
			print()
main()


a = ['-1', '-1', '-1', '555', '-1', '33333', '555555', '-1']
t = int(input())
for i in range(t):
	n = int(input())
	if n < 8:
		print(a[n])
	else:
		n5 = n // 3
		n3 = 0
		if n % 3 == 2:
			n5 -= 1
			n3 += 1
		if n % 3 == 1:
			n5 -= 3
			n3 += 2
		s = '5' * 3 * n5 + '3' * 5 * n3
		print(s)


t = int(input())
for i in range(t):
	n = int(input())
	m = n % 3
	if m == 2:
		if n < 5:
			print(-1)
		else:
			print((n - m - 3) * '5' + 5 * '3')
	elif m == 1:
		if n < 10:
			print(-1)
		else:
			print((n - m - 9) * '5' + 10 * '3')
	else:
		print(n * '5')


testcase = int(input())
for i in range(testcase):
	size = int(input())
	out = ''
	k = 0
	while size % 3 != 0 or (k % 5 != 0 and size >= 0):
		size -= 1
		k += 1
	if size < 0:
		print(-1)
	else:
		print(''.join(('5' for i in range(size))) + ''.join(('3' for i in range(k))))


n = int(input())
for i in range(n):
	N = int(input())
	found = False
	for j in range(N + 1):
		if (N - j) % 3 == 0:
			if j % 5 == 0:
				print(str(5) * (N - j) + str(3) * j)
				found = True
				break
	if not found:
		print(-1)


T = int(input())
vals = []
maxVal = 0
for i in range(T):
	vals.append(int(input()))
	if vals[i] > maxVal:
		maxVal = vals[i]
n = [-1, -1, 3, -1, 0]
for i in range(5, maxVal):
	if n[i - 3] == -1 and n[i - 5] == -1:
		n.append(-1)
	elif n[i - 3] == -1:
		n.append(n[i - 5])
	elif n[i - 5] == -1:
		n.append(n[i - 3] + 3)
	else:
		n.append(max(n[i - 3] + 3, n[i - 5]))
for i in vals:
	if n[i - 1] == -1:
		print(-1)
	else:
		for j in range(n[i - 1]):
			print(5, end='')
		for j in range(n[i - 1], i):
			print(3, end='')
		print()


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N < 3:
		print(-1)
	else:
		k = N - N % 3
		if k < N:
			while k > 0 and (N - k) % 5 > 0:
				k -= 3
		if (N - k) % 5 == 0:
			print('5' * k + '3' * (N - k))
		else:
			print(-1)


def func(n):
	r = n % 3
	if r == 0:
		return (n, 0)
	elif r == 1:
		return (n - 10, 10)
	elif r == 2:
		return (n - 5, 5)
t = int(input())
for i in range(t):
	(a, b) = func(int(input()))
	if a < 0:
		print(-1)
	else:
		print('5' * a + '3' * b)


def decentFinder(n):
	if n < 3:
		return '-1'
	elif n % 3 == 0:
		return '5' * n
	else:
		p = n
		countThrees = 0
		while p > 0:
			p -= 5
			countThrees += 5
			if p < 0:
				break
			if p % 3 == 0:
				return '5' * p + '3' * countThrees
		p = n
		countFives = 0
		while p > 0:
			p -= 3
			countFives += 3
			if p < 0:
				break
			if p % 3 == 0:
				return '5' * p + '3' * countFives
		return '-1'
t = int(input())
b = []
for j in range(0, t):
	print(decentFinder(int(input())))


from math import floor

def sherlock(N):
	for j in range(0, N + 1, 5):
		if (N - j) % 3 == 0:
			return '5' * (N - j) + '3' * j
	return -1

def main():
	T = int(input())
	for i in range(T):
		N = int(input())
		s = sherlock(N)
		print(s)
main()


t = int(input())
for u in range(t):
	n = int(input())
	if n < 3:
		print(-1)
	else:
		r = n % 3
		c = int(n / 3)
		if r == 0:
			three = c
			five = 0
		elif r == 1:
			three = max(c - 3, 0)
			five = 2
		else:
			three = max(c - 1, 0)
			five = 1
		if three * 3 + five * 5 == n:
			mes = ''
			for i in range(three):
				mes += '555'
			for i in range(five):
				mes += '33333'
			print(mes)
		else:
			print(-1)


num = int(input())
for j in range(0, num):
	N = int(input())
	fives = -1
	for i in range(0, N + 1):
		if i % 3 == 0 and (N - i) % 5 == 0:
			fives = i
	if fives > -1:
		print('5' * fives + '3' * (N - fives))
	else:
		print('-1')


t = int(input())
for i in range(t):
	k = int(input())
	text = -1
	for x in range(k // 5 + 1):
		if (k - 5 * x) % 3 == 0:
			y = (k - 5 * x) // 3
			text = ''.join(3 * y * ['5']) + ''.join(5 * x * ['3'])
			break
	print(text)


def function(k):
	num = ''
	while (k - len(num)) % 3 != 0:
		num = num + '33333'
		if len(num) > k:
			print(-1)
			return
	num = (k - len(num)) * '5' + num
	print(num)
T = int(input())
for i in range(T):
	function(int(input()))


for i in range(int(input())):
	n = int(input())
	max3 = -1
	for j in range(n // 3 + 1):
		if j > 0 and (n - j * 3) % 5 == 0 or (j == 0 and n % 5 == 0):
			if j > max3:
				max3 = j
	res = ''
	if max3 > -1:
		res = res.ljust(max3 * 3, '5')
		res = res.ljust(n, '3')
	else:
		res = '-1'
	print(res)


def number(n5, n3):
	print(''.join([''.join(['5'] * n5), ''.join(['3'] * n3)]))
T = int(input())
for t in range(T):
	N = int(input())
	r = N % 3
	if r == 0:
		number(N, 0)
	elif r == 1 and N >= 10:
		number(N - 10, 10)
	elif r == 2 and N >= 5:
		number(N - 5, 5)
	else:
		print(-1)


N = int(input())
res = list()
for i in range(N):
	num = int(input())
	tmp_res = [0, 0]
	while num > 0:
		if num % 3 == 0:
			tmp_res[0] = num // 3
			num = 0
		else:
			num -= 5
			tmp_res[1] += 1
	if num >= 0:
		res.append(int('555' * tmp_res[0] + '33333' * tmp_res[1]))
	else:
		res.append(-1)
for el in res:
	print(el)


import sys
input = list(sys.stdin)
for line in input[1:]:
	n = int(line)
	k = 0
	r = None
	while k * 3 <= n:
		if (n - k * 3) % 5 == 0:
			r = k * 3
		k += 1
	if not r:
		if n % 5 == 0:
			print('3' * n)
		else:
			print('-1')
	else:
		print('5' * r, '3' * (n - r), sep='')


__author__ = 'Murugan'

def getDecent(x, y):
	if x < 0:
		return [-1, -1]
	elif x % 3 == 0:
		return [x, y]
	else:
		return getDecent(x - 5, y + 5)

def getLargestDecent(N):
	str = '-1'
	if N < 3:
		str = '-1'
	elif N % 3 == 0:
		str = '5' * N
	else:
		xy = getDecent(N, 0)
		if xy[0] == -1:
			str = '-1'
		else:
			str = '5' * xy[0] + '3' * xy[1]
	return str
T = int(input())
for i in range(T):
	N = int(input())
	print(getLargestDecent(N))


t = int(input())
for _ in range(t):
	n = int(input())
	k2 = 0
	k1 = 1
	while k1 >= 0:
		if (n - 5 * k2) % 3 == 0:
			break
		k1 = (n - 5 * k2) // 3
		k2 += 1
	k1 = (n - 5 * k2) // 3
	if k1 >= 0:
		for i in range(3 * k1):
			print('5', end='')
		for i in range(5 * k2):
			print('3', end='')
	else:
		print('-1', end='')
	print()


import sys
import math
T = int(sys.stdin.readline())
Ks = []
for index in range(T):
	Ks.append(int(sys.stdin.readline()))
for k in Ks:
	l = math.floor(k / 5)
	solutions = []
	for element in range(l + 1):
		remain = k - element * 5
		if remain % 3 == 0:
			hit = remain // 3
			solutions.append((element * 5, hit * 3))
	try:
		choice = solutions[0]
		for element in solutions:
			if element[1] > choice[1]:
				choice = element
		string = ''
		for index in range(choice[1]):
			string += '5'
		for index in range(choice[0]):
			string += '3'
		print(string)
	except IndexError:
		print('-1')


T = int(input())
for i in range(T):
	n = int(input())
	for n5 in range(3 * (n // 3), -1, -3):
		n3 = n - n5
		if n3 % 5 == 0:
			print(n5 * '5' + n3 * '3')
			break
	else:
		print(-1)


def fun():
	test = input()
	test1 = int(test)
	for i in range(test1):
		x = input()
		x1 = int(x)
		(c1, c2) = (0, 0)
		n = int(x1 / 3) + 1
		a = '5'
		b = '3'
		for j in range(n):
			if x1 % 3 == 0 and x1 > 0:
				c1 = int(x1 / 3)
				break
			if x1 == 0:
				break
			x1 = x1 - 5
			c2 += 1
		if x1 >= 0:
			c1 = c1 * 3
			c2 = c2 * 5
			s = a * c1 + b * c2
			s1 = int(s)
			print(s1)
		else:
			print(-1)
fun()


import sys

def best_split(digits):
	s = []
	for i in range(digits + 1):
		if i % 3 == 0 and (digits - i) % 5 == 0:
			s.append(i)
	if s:
		return max(s)
	else:
		return None

def decent_num(digits):
	split = best_split(digits)
	if split == None:
		return -1
	else:
		s1 = '5' * split
		s2 = '3' * (digits - split)
		return int(s1 + s2)
sys.stdin.readline()
for l in sys.stdin:
	n = int(l)
	print(decent_num(n))


t = int(input())
while t:
	t -= 1
	n = int(input())
	i = 0
	while (n - 5 * i) % 3 != 0 and n - 5 * i >= 0:
		i += 1
	if i == 5:
		if n % 5 == 0:
			print('3' * n)
		else:
			print(-1)
	elif n >= 5 * i:
		print('5' * (n - 5 * i) + '3' * (5 * i))
	else:
		print(-1)


T = int(input())
for t in range(0, T):
	N = int(input())
	n3 = -N % 3
	n5 = (N - n3 * 5) // 3
	if n5 < 0:
		print('-1')
	else:
		print(''.join(['555'] * n5 + ['33333'] * n3))


from collections import Counter

def isDecent(n):
	d = n
	f = 0
	t = 0
	while d > 0:
		if d % 3 == 0:
			f = d
			break
		d -= 5
	t = n - d
	if d < 0 or t % 5 != 0:
		return '-1'
	return '5' * f + '3' * t
(inps, decents) = ([], [])
for i in range(int(input())):
	inps.append(int(input()))
for inp in inps:
	decents.append(isDecent(inp))
for decent in decents:
	print(decent)


T = int(input())
for case in range(T):
	N = int(input())
	for num3 in range(N + 1):
		num5 = N - num3
		if num5 % 3 == 0 and num3 % 5 == 0:
			print('5' * num5 + '3' * num3)
			break
	else:
		print(-1)


t = int(input())

def val(k):
	n3 = 0
	while k >= 0:
		if k % 3 == 0:
			return '5' * k + '3' * n3
		else:
			k -= 5
			n3 += 5
	return '-1'
for _ in range(t):
	print(val(int(input())))


import sys

def large_decent(n):
	fives = [i for i in range(0, n + 1, 3) if (n - i) % 5 == 0]
	if fives:
		return int(max(fives) * '5' + (n - max(fives)) * '3')
	else:
		return -1

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		print(large_decent(int(sys.stdin.readline())))
main()


import sys

def main():
	testcases = int(sys.stdin.readline())
	testcase_list = []
	for testcase in range(testcases):
		testcase_list.append(int(sys.stdin.readline()))
	for testcase in testcase_list:
		decent_number(testcase)
		print()

def decent_number(k):
	if k < 3:
		print(-1, end='')
		return
	elif k % 3 == 0:
		for i in range(k):
			print('5', end='')
		return
	else:
		n3 = 0
		while k > 3:
			k -= 5
			n3 += 5
			if k % 3 == 0:
				for i in range(k):
					print('5', end='')
				for i in range(n3):
					print('3', end='')
				return
		print(-1, end='')
main()


import sys

def solve(num_fives, num_threes):
	if num_fives % 3 == 0:
		return (True, num_fives, num_threes)
	elif num_fives < 5:
		return (False, 0, 0)
	else:
		return solve(num_fives - 5, num_threes + 5)
T = int(sys.stdin.readline())
for case in range(T):
	N = int(sys.stdin.readline())
	(possible, num_fives, num_threes) = solve(N, 0)
	print(-1) if not possible else print(num_fives * '5' + num_threes * '3')


h = int(input())
c = 0
while h > c:
	n = int(input())
	q = n
	th = ''
	fi = ''
	num = ''
	g = 0
	for f in range(q):
		if f * 3 + (q - f * 3) == q and (q - f * 3) % 5 == 0:
			if q - f * 3 > 0:
				g = f
	if g != 0 and q % 3 != 0:
		print(g * '555' + (q - g * 3) * '3')
	elif q % 15 == 0:
		print(q * '5')
	elif q % 5 == 0:
		print(q * '3')
	elif q % 3 == 0:
		print(q * '5')
	else:
		print('-1')
	c += 1


import sys

def compose(n, f, t=0):
	s = 3 * f + 5 * t
	if s == n:
		return '5' * 3 * f + '3' * 5 * t
	if n < 3:
		return -1
	if s < n:
		return compose(n, f, t + 1)
	if f > 0 and s > n:
		return compose(n, f - 1, t)
	if f == 0 and s > n:
		return -1
	else:
		return -1
test_count = int(sys.stdin.readline())
for i in range(test_count):
	test_case = int(sys.stdin.readline())
	sys.stdout.write(str(compose(test_case, test_case // 3)) + '\n')


import sys
f = sys.stdin
size = int(f.readline())
i = 0
while i < size:
	val = int(f.readline())
	tmp = val
	if val < 3:
		print(-1)
	elif val % 3 == 0:
		print('555' * int(val / 3))
	else:
		fives = ''
		threes = ''
		while not val % 3 == 0:
			val = val - 5
			threes += '33333'
		fives = '555' * int(val / 3)
		str = fives + threes
		if not len(str) == tmp:
			print(-1)
		else:
			print(str)
	i += 1


def decent(N):
	if N == 0:
		return ''
	elif N % 3 == 0:
		return N // 3 * '555'
	else:
		return str(decent(N - 5)) + '33333'
T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	if N < 3 or N == 4 or N == 7:
		print(-1)
	else:
		print(decent(N))


import sys

def dng(N):
	el = '555'
	el1 = '33333'
	if N % 3 == 0:
		return int(el * (N // 3))
	elif N == 5 or N == 10:
		return int(el1 * (N // 5))
	else:
		count = N
		subtract = 5
		while subtract < count:
			if (count - subtract) % 3 == 0:
				return int(el * ((count - subtract) // 3) + el1 * (subtract // 5))
			subtract += subtract
		return -1

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		print(dng(int(sys.stdin.readline())))
main()


T = int(input())
for i in range(T):
	N = int(input())
	x = 0
	y = 0
	while ((N - 5 * x) % 3 != 0) & (y >= 0):
		x += 1
		y = (N - 5 * x) / 3
	y = (N - 5 * x) / 3
	if y < 0:
		print(-1)
	else:
		print('5' * (3 * int(y)) + '3' * (5 * int(x)))


T = int(input())
for _ in range(T):
	N = int(input())
	if N < 3:
		print(-1)
	else:
		k = N - N % 3
		if k < N:
			while k > 0 and (N - k) % 5 > 0:
				k -= 3
		if (N - k) % 5 == 0:
			print('5' * k + '3' * (N - k))
		else:
			print(-1)


import sys
T = int(sys.stdin.readline())
list = []
for i in range(T):
	list.append(int(sys.stdin.readline()))
for item in list:
	i = 0
	answer = -1
	while i <= item:
		b = item - i
		a = i
		if b % 3 == 0:
			answer = int(b * '5' + a * '3')
			break
		else:
			i += 5
	print(answer)


import sys

def constructLargestDecentNum(fives, threes):
	numString = ''
	numString = numString + int(fives) * '5'
	numString = numString + int(threes) * '3'
	return int(numString)

def getDecentNum(N):
	iterations = int(N / 5)
	numFives = -1
	numThrees = -1
	for i in range(iterations + 1):
		if (N - 5 * i) % 3 == 0:
			numFives = N - 5 * i
			numThrees = i * 5
			break
	if numFives + numThrees < 0:
		return -1
	else:
		return constructLargestDecentNum(numFives, numThrees)
lines = []
for line in sys.stdin:
	lines.append(line)
T = int(lines[0])
Ns = lines[1:]
for i in range(T):
	Ns[i] = int(Ns[i])
for N in Ns:
	print(getDecentNum(N))


for i in range(int(input())):
	ndig = int(input())
	if ndig in [1, 2, 4, 7]:
		print(-1)
	else:
		n5 = 3 * int(ndig / 3)
		n3 = ndig - n5
		while n3 % 5 != 0:
			n5 -= 3
			n3 += 3
		print(n5 * '5' + n3 * '3')


from sys import stdin
t = int(stdin.readline())
for i in range(t):
	n = int(stdin.readline())
	if n % 3 == 0:
		print('5' * 3 * (n // 3))
	else:
		(x, y, solved) = (n // 3, 0, False)
		while x >= 0 and (not solved):
			y = (n - 3 * x) // 5
			if 3 * x + 5 * y == n:
				solved = True
			else:
				x -= 1
		if solved:
			print('5' * 3 * x + '3' * 5 * y)
		else:
			print('-1')


def main():
	n = int(input())
	for i in range(n):
		x = int(input())
		m = x % 3
		if m == 0:
			print('5' * x)
			continue
		x -= m
		for j in range(4):
			x -= 3
			m += 3
			if x >= 0:
				if m % 5 == 0:
					print('5' * x + '3' * m)
					break
			else:
				print(-1)
				break
main()


t = int(input())

def solve(n):
	if n < 3:
		print('-1')
	elif n % 3 == 0:
		print('5' * n)
	elif n < 5:
		print('-1')
	elif n % 5 == 0 and (n == 5 or n == 10):
		print('3' * n)
	elif n < 8:
		print('-1')
	else:
		y = n // 3
		x = 1
		(a, b) = (5, 3)
		while True:
			guess = 5 * x + 3 * y
			if guess == n:
				print('5' * b + '3' * a)
				return
			elif guess - n == 3:
				y = y - 1
				a = a * x
				b = b * y
			elif guess - n == 4:
				x = x + 1
				y = y - 3
				a = a * x
				b = b * y
for test in range(t):
	n = int(input())
	solve(n)


def max_decent(N):
	f = N - N % 3
	while f >= 0:
		t = N - f
		if t % 5 == 0:
			return '5' * f + '3' * t
		f -= 3
	return -1
T = int(input().strip())
cases = [int(input().strip()) for i in range(T)]
for N in cases:
	print(max_decent(N))


def decent_number(N):
	digits = []
	while len(digits) < N:
		digits.extend([5, 5, 5])
	if len(digits) > N:
		while digits:
			digits = digits[:-3]
			if (N - len(digits)) % 5 == 0:
				digits.extend([3] * (N - len(digits)))
				break
	try:
		return int(''.join((str(d) for d in digits)))
	except ValueError:
		return -1
for test in range(int(input())):
	print(decent_number(int(input())))


T = int(input())
for i in range(T):
	N = int(input())
	if N % 3 == 0:
		for i in range(N):
			print('5', end='')
		print('')
	elif N % 3 == 2 and N >= 5:
		for i in range(N - 5):
			print('5', end='')
		for i in range(5):
			print('3', end='')
		print('')
	elif N % 3 == 1 and N >= 10:
		for i in range(N - 10):
			print('5', end='')
		for i in range(10):
			print('3', end='')
		print('')
	else:
		print('-1')


import math
T = int(input())
for i in range(0, T):
	N = int(input())
	if N < 3:
		print(-1)
	else:
		ans = -1
		for y in range(0, int(N / 5) + 1):
			x = (float(N) - 5 * float(y)) / 3.0
			if math.ceil(x) == x:
				num = str(5) * int(x) * 3 + str(3) * int(y) * 5
				if int(num) > ans and len(num) == N:
					ans = int(num)
					break
		print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	threes = {0: 0, 1: 10, 2: 5}[N % 3]
	fives = N - threes
	if fives < 0:
		print(-1)
	else:
		print('5' * fives + '3' * threes)


numTests = int(input())
for _ in range(0, numTests):
	digits = int(input())
	x = 0
	y = 0
	while (digits - 5 * x) % 3 != 0 and y >= 0:
		x += 1
		y = (digits - 5 * x) // 3
	y = (digits - 5 * x) // 3
	if y < 0:
		print('-1')
	else:
		print(''.join(('5' for i in range(3 * y))) + ''.join(('3' for j in range(5 * x))))


T = int(input())
for t in range(T):
	n = int(input())
	rem = n % 3
	(a, b) = (0, n // 3)
	if rem == 0:
		pass
	elif rem == 1:
		b -= 3
		a = 2
	else:
		b -= 1
		a = 1
	if b < 0:
		print(-1)
	else:
		print('5' * b * 3 + '3' * a * 5)


tc = int(input())
for c in range(tc):
	n = int(input())
	x = n
	y = 0
	ans = -1
	while x >= 0:
		if x % 3 == 0 and y % 5 == 0:
			ans = 1
			break
		x = x - 1
		y = y + 1
	if ans == -1:
		print(-1)
		continue
	for i in range(x):
		print('5', end='')
	for i in range(y):
		print('3', end='')
	print('')


tests = int(input())
for i in range(tests):
	digits = int(input())
	z = None
	if digits == 1:
		print(-1)
		continue
	if digits % 3 == 0:
		print('5' * digits)
	else:
		num = 0
		b = digits
		while b >= 0:
			b = b - 5
			num += 5
			if b % 3 == 0 and b >= 0:
				print('5' * b + '3' * num)
				z = 7
				break
		if z == None:
			print(-1)


for bita3 in range(int(input())):
	k = int(input())
	if k % 3 == 0:
		print('5' * k)
		continue
	if k % 3 == 1:
		if k < 10:
			print(-1)
			continue
		else:
			no_of_3 = 10
			no_of_5 = k - no_of_3
			print('5' * no_of_5 + '3' * no_of_3)
			continue
	if k % 3 == 2:
		if k < 5:
			print(-1)
			continue
		else:
			no_of_3 = 5
			no_of_5 = k - no_of_3
			print('5' * no_of_5 + '3' * no_of_3)
			continue


import fileinput

def get_largest_decent(digits):
	result = ''
	remaining = digits
	while remaining >= 3:
		if remaining % 3 == 0:
			return '5' * remaining + result
		elif remaining >= 5:
			result = '3' * 5 + result
			remaining -= 5
		else:
			return '-1'
	if remaining != 0:
		return '-1'
	else:
		return result
for line in fileinput.input():
	if fileinput.lineno() != 1:
		print(get_largest_decent(int(line)))


a = eval(input())
for i in range(a):
	k = eval(input())
	max_a = k // 3
	while True:
		n_5 = max_a * 3
		n_3 = k - n_5
		if n_3 % 5 == 0:
			print('5' * n_5 + '3' * n_3)
			break
		else:
			max_a -= 1
		if max_a == -1:
			print('-1')
			break


T = int(input())
for t in range(T):
	N = int(input())
	threes = 0
	fives = N // 3 * 3
	if fives == N:
		print('5' * fives)
	elif fives > 0:
		while fives > 0 and (N - fives) % 5 != 0:
			fives -= 3
		threes = N - fives
		if threes % 5 != 0:
			print(-1)
		else:
			print('5' * fives + '3' * threes)
	elif N % 5 == 0:
		print('3' * N)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	for n5 in range(n - n % 3, -1, -3):
		n3 = n - n5
		if n3 % 5 == 0:
			print('5' * n5 + '3' * n3)
			break
		if n5 == 0:
			print(-1)


numCases = int(input())
for x in range(0, numCases):
	inp = int(input())
	if inp < 3:
		print('-1')
		continue
	threes = 0
	fives = 0
	solved = False
	while 5 * threes + 3 * fives <= inp:
		rem = int(inp - threes * 5)
		if rem >= 0 and rem % 3 == 0:
			solved = True
			fives = int(rem / 3)
			break
		else:
			threes += 1
	if solved:
		output = '5' * 3 * fives + '3' * 5 * threes
		print(output)
	else:
		print('-1')


for i in range(int(input())):
	N = int(input())
	n3 = N % 3
	n5 = N - n3
	while n3 % 5 != 0:
		n5 -= 3
		n3 += 3
		if n5 < 0:
			print('-1')
			break
	else:
		print('5' * n5 + '3' * n3)


T = int(input())
for _ in range(T):
	N = int(input())
	fives = N
	threes = 0
	while fives > 0 and fives % 3 > 0:
		fives -= 5
		threes += 5
	if fives >= 0:
		result = '5' * fives + '3' * threes
	else:
		result = '-1'
	print(result)


tests = int(input())

def get_decent(n):
	if n % 3 == 0:
		return build_decent(n, 0)
	if n % 3 == 2:
		if n - 5 < 0:
			return -1
		else:
			return build_decent(n - 5, 5)
	if n % 3 == 1:
		if n - 10 < 0:
			return -1
		else:
			return build_decent(n - 10, 10)
	return -1

def build_decent(n_of_5, n_of_3):
	decent = ''
	for i in range(n_of_5):
		decent += '5'
	for i in range(n_of_3):
		decent += '3'
	return int(decent)
for t in range(tests):
	n = int(input())
	print(get_decent(n))


def is_decent(num):
	if len(set(num)) != 0 and set(num).issubset({'3', '5'}):
		if num.count('5') % 3 == 0:
			if num.count('3') % 5 == 0:
				return True
	return False

def find_largest_decent(N):
	largest = list('5' * N)
	if is_decent(''.join(largest)):
		return ''.join(largest)
	else:
		for j in range(len(largest) - 1, -1, -1):
			largest[j] = '3'
			if is_decent(''.join(largest)):
				return ''.join(largest)
		else:
			return -1
T = int(input())
for i in range(T):
	N = int(input())
	print(find_largest_decent(N))


t = int(input())
n = []
for i in range(t):
	q = int(input())
	n.append(q)
for i in range(len(n)):
	final = []
	m = int(n[i])
	if m < 3 or m == 4 or m == 7:
		print(-1)
	elif m % 3 == 0:
		for x in range(m):
			final.append(5)
		print(''.join((str(i) for i in final)))
	elif m % 3 == 1:
		for x in range(m - 10):
			final.append(5)
		for x in range(10):
			final.append(3)
		print(''.join((str(i) for i in final)))
	else:
		for x in range(m - 5):
			final.append(5)
		for x in range(5):
			final.append(3)
		print(''.join((str(i) for i in final)))


T = input()
inputs = list()
for i in range(int(T)):
	temp = input()
	inputs.append(int(temp))
for i in inputs:
	if i % 3 == 0:
		print('5' * i)
	v1 = int(i / 3)
	v1 = 3 * v1
	v2 = i - v1
	while v2 % 5 != 0:
		v1 = v1 - 3
		v2 = v2 + 3
		if v1 < 0:
			print('-1')
			break
		elif v2 % 5 == 0:
			print('5' * v1 + '3' * v2)
			break


def findDecent(n):
	if n == 0:
		return '-1'
	residual = n % 3
	reductions = 0
	while residual % 5 != 0 or residual > n:
		residual += 3
		if residual > n:
			return '-1'
	return '5' * (n - residual) + '3' * residual
cases = int(input())
tests = [int(input()) for _ in range(cases)]
for test in tests:
	print(findDecent(test))


T = int(input())
for t in range(T):
	N = int(input())
	mdn = -1
	n5 = N // 3
	while n5 >= 0:
		N5 = 3 * n5
		N3 = N - N5
		if N3 % 5 == 0:
			mdn = '5' * N5 + '3' * N3
			break
		n5 -= 1
	print(mdn)


T = int(input())
for t in range(T):
	N = int(input())
	threes = N % 3
	fives = N - threes
	while fives % 3 != 0 or threes % 5 != 0:
		fives -= 3
		threes += 3
	if fives < 0:
		print(-1)
	else:
		print('5' * fives + '3' * threes)


T = int(input())
for i in range(T):
	N = int(input())
	tempN = N
	threes = 0
	fives = 0
	result = ''
	while tempN > 0:
		if tempN % 3 == 0:
			fives = tempN
			break
		tempN -= 5
	threes = N - tempN
	if threes % 5 != 0 or tempN < 0:
		print('-1')
		continue
	for i in range(fives):
		result += '5'
	for i in range(threes):
		result += '3'
	print(result)


T = int(input())
for t in range(T):
	N = int(input())
	found = False
	for x in range(0, N + 1, 5):
		y = N - x
		if y % 3 == 0:
			print(''.join(['5'] * y) + ''.join(['3'] * x))
			found = True
			break
	if not found:
		print('-1')


t = int(input())
for _ in range(t):
	n = int(input())
	ans = None
	for k in range(n // 3, -1, -1):
		if (n - 3 * k) % 5 == 0:
			ans = (k, (n - 3 * k) // 5)
			break
	print(''.join(['555'] * ans[0] + ['33333'] * ans[1]) if ans else -1)


def solve(n):
	m = n
	while m > 0 and m % 3 != 0:
		m -= 5
	if m < 0:
		return -1
	else:
		return '5' * m + '3' * (n - m)
T = int(input())
for _ in range(T):
	print(solve(int(input())))


T = int(input())
for i in range(T):
	N = int(input())
	if N < 3 or N == 4 or N == 7:
		print(-1)
	else:
		res = ''
		if N % 3 == 0:
			for i in range(N):
				res += '5'
		elif N % 3 == 2:
			for i in range(N - 5):
				res += '5'
			res += '33333'
		else:
			for i in range(N - 10):
				res += '5'
			res += '3333333333'
		print(int(res))


import sys

def printResult(n5er, n3er):
	print('5' * n5er + '3' * n3er)

def foundIt(n):
	debug = False
	n5er = 0
	n3er = 0
	while n5er < n:
		n5er += 3
		if debug:
			print(n5er)
	if n % n5er == 0:
		printResult(n5er, n3er)
		return True
	n5er -= 3
	if debug:
		print('---- 1')
	n_rest = n - n5er
	while n3er < n_rest:
		n3er += 5
		if debug:
			print(n3er)
	if n_rest % n3er == 0:
		printResult(n5er, n3er)
		return True
	n3er -= 5
	if debug:
		print('---- 2')
	if debug:
		print(str(n5er) + ' ' + str(n3er))
	if debug:
		print('---- 3')
	while n5er > 0:
		n5er -= 3
		n_rest = n - n5er
		if debug:
			print('n5er: ' + str(n5er))
		if debug:
			print('n_rest: ' + str(n_rest))
		n3er = 0
		while n3er < n_rest:
			n3er += 5
		if n_rest % n3er == 0:
			printResult(n5er, n3er)
			return True
		if debug:
			print(str(n5er) + ' ' + str(n3er))
	return False
i = 0
for line in sys.stdin:
	if i != 0 and (not foundIt(int(line))):
		print('-1')
	i += 1


import sys

def factorize(n):
	multiple_of_3 = n
	if n == 0:
		return -1
	while multiple_of_3 > 3 and multiple_of_3 % 3 != 0:
		multiple_of_3 -= 5
	if multiple_of_3 < 0 or multiple_of_3 % 3 != 0:
		return -1
	return multiple_of_3
sys.stdin.readline()
for line in sys.stdin.readlines():
	n = int(line)
	multiple_of_3 = factorize(n)
	if multiple_of_3 >= 0:
		multiple_of_5 = n - multiple_of_3
		print(str(5) * multiple_of_3 + str(3) * multiple_of_5)
	else:
		print(-1)


num_testcase = int(input())
for i_testcase in range(num_testcase):
	num_digit = int(input())
	num_three = 0
	while num_three <= num_digit:
		if (num_digit - num_three) % 3 == 0:
			print('5' * (num_digit - num_three) + '3' * num_three)
			break
		num_three += 5
	if num_three > num_digit:
		print(-1)


def decent_number(N):
	for fives in range(N, -1, -1):
		threes = N - fives
		if fives % 3 == 0 and threes % 5 == 0:
			return '5' * fives + '3' * threes
	return '-1'

def main():
	import sys
	(count, *Ns) = sys.stdin.readlines()
	for N in Ns:
		print(decent_number(int(N)))
main()


import sys
import itertools
inp = iter(sys.stdin)

def read_line():
	return int(next(inp))

def resolve(num):
	kq = ''
	timeForFive = num // 3 * 3
	timeForThree = num - timeForFive if timeForFive > 1 else 0
	while timeForFive and timeForThree % 5 != 0:
		timeForFive -= 3
		timeForThree += 3
	if timeForFive and timeForThree:
		kq += '5' * timeForFive + '3' * timeForThree
	elif timeForFive == num:
		kq += '5' * num
	elif timeForThree == num and timeForThree % 5 == 0 and (not timeForFive):
		kq += '3' * num
	else:
		kq += '-1'
	return kq
n_cases = read_line()
for _ in range(n_cases):
	num = read_line()
	print(resolve(num))


testcases = int(input())
for i in range(testcases):
	no_of_five = 0
	no_of_three = 0
	n = int(input())
	if n % 3 == 0:
		no_of_five = n // 3
	else:
		no_of_five = n // 3
		while (n - 3 * no_of_five) % 5 != 0 and no_of_five >= 0:
			no_of_five = no_of_five - 1
		no_of_three = (n - 3 * no_of_five) // 5
	if 3 * no_of_five + 5 * no_of_three != n or no_of_five < 0:
		print(-1)
	else:
		result = 3 * no_of_five * str(5) + 5 * no_of_three * str(3)
		print(result)