After completing some serious investigation, Watson and Holmes are now chilling themselves in the Shimla hills. Very soon Holmes became bored. Holmes lived entirely for his profession. We know he is a workaholic. So Holmes wants to stop his vacation and get back to work. But after a tiresome season, Watson is in no mood to return soon. So to keep Holmes engaged, he decided to give Holmes one math problem. And Holmes agreed to solve the problem and said as soon as he solves the problem, they should return back to work. Watson too agreed. 
The problem was as follows. Watson knows Holmes’ favorite numbers are 6 and 5. So he decided to give Holmes N  single digit numbers. Watson asked Holmes to form a new number with the given N numbers in such a way that the newly formed number should be completely divisible by 5 and 6. Watson told Holmes that he should also form the number from these digits in such a way that the formed number is maximum. He may or may not use all the given numbers. But he is not allowed to use leading zeros. Though he is allowed to leave out some of the numbers, he is not allowed to add any extra numbers, which means the maximum count of each digit in the newly formed number, is the same as the number of times that number is present in those given N digits.

-----Input-----
The first line of input contains one integers T denoting the number of test cases.
Each test case consists of one integer N, number of numbers.
Next line contains contains N single digit integers 

-----Output-----
For each test case output a single number, where the above said conditions are satisfied. If it is not possible to create such a number with the given constraints print -1.If there exists a solution, the maximised number should be greater than or equal to 0. 

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 10000
- 0 ≤ Each digit ≤ 9

-----Subtasks-----
Subtask #1 : (90 points)
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 10000

Subtask 2 : (10 points) 

- 1 ≤ T ≤ 10
- 1 ≤ N≤ 10

-----Example-----
Input:
2
12
3 1 2 3 2 0 2 2 2 0 2 3
11
3 9 9 6 4 3 6 4 9 6 0

Output:
33322222200
999666330

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = int(input())
for i in range(0, t):
	n = int(input())
	lis = list(map(int, input().split()))
	lis2 = []
	for j in range(0, 10):
		lis2.append(0)
	for j in range(0, len(lis)):
		lis2[lis[j]] += 1
	s = sum(lis)
	while s % 3 != 0:
		if s % 3 == 2:
			if lis2[2] >= 1:
				lis2[2] -= 1
				s = s - 2
			elif lis2[5] >= 1:
				lis2[5] -= 1
				s = s - 5
			elif lis2[8] >= 1:
				lis2[8] -= 1
				s = s - 8
			elif lis2[1] >= 2:
				lis2[1] -= 2
				s = s - 2
			elif lis2[1] >= 1 and lis2[4] >= 1:
				lis2[1] -= 1
				lis2[4] -= 1
				s = s - 5
			elif lis2[4] >= 2:
				lis2[4] -= 2
				s = s - 8
			elif lis2[1] >= 1 and lis2[7] >= 1:
				lis2[1] -= 1
				lis2[7] -= 1
				s = s - 8
			elif lis2[4] >= 1 and lis2[7] >= 1:
				lis2[4] -= 1
				lis2[7] -= 1
				s = s - 11
			elif lis2[7] >= 2:
				lis2[7] -= 2
				s = s - 14
		elif s % 3 == 1:
			if lis2[1] >= 1:
				lis2[1] -= 1
				s = s - 1
			elif lis2[4] >= 1:
				lis2[4] -= 1
				s = s - 4
			elif lis2[7] >= 1:
				lis2[7] -= 1
				s = s - 7
			elif lis2[2] >= 2:
				lis2[2] -= 2
				s = s - 4
			elif lis2[5] >= 1 and lis2[2] >= 1:
				lis2[2] -= 1
				lis2[5] -= 1
				s = s - 7
			elif lis2[5] >= 2:
				lis2[5] -= 2
				s = s - 10
			elif lis2[2] >= 1 and lis2[8] >= 1:
				lis2[2] -= 1
				lis2[8] -= 1
				s = s - 10
			elif lis2[8] >= 1 and lis2[5] >= 1:
				lis2[8] -= 1
				lis2[5] -= 1
				s = s - 13
			elif lis2[8] >= 2:
				lis2[8] -= 2
				s = s - 16
	lis3 = []
	for j in range(1, 10):
		if lis2[j] >= 1:
			for k in range(0, lis2[j]):
				lis3.append(j)
	lis3.reverse()
	for k in range(0, lis2[0]):
		lis3.append(0)
	sol = ''
	for k in range(0, len(lis3)):
		sol += str(lis3[k])
	print(sol)


def mul3(ip):
	q0 = []
	q1 = []
	q2 = []
	ip.sort()
	sums = sum(ip)
	for i in ip:
		if i % 3 == 0:
			q0.insert(0, i)
		if i % 3 == 1:
			q1.insert(0, i)
		if i % 3 == 2:
			q2.insert(0, i)
	if sums % 3 == 1:
		if len(q1):
			q1.pop()
		elif len(q2) >= 2:
			q2.pop()
			q2.pop()
		else:
			return -1
	elif sums % 3 == 2:
		if len(q2):
			q2.pop()
		elif len(q1) >= 2:
			q1.pop()
			q1.pop()
		else:
			return -1
	q0.extend(q1)
	q0.extend(q2)
	if len(q0) <= 0:
		return -1
	q0.sort()
	q0.reverse()
	return q0
t = int(input())
for z in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if 0 not in a or mul3(a) == -1:
		print(-1)
	else:
		out = ''
		temp = mul3(a)
		for p in temp:
			out += str(p)
		print(out)


t = eval(input())
while t:
	n = eval(input())
	z = list(map(int, input().split()))
	a = [0] * 10
	for i in z:
		a[i] += 1
	if a[0] == 0:
		print(-1)
	else:
		no_1 = a[1] + a[4] + a[7]
		no_2 = a[2] + a[5] + a[8]
		s = ''
		if (no_1 + no_2 * 2) % 3 == 0:
			s = ''
		elif no_2 > no_1:
			no = (no_2 - no_1) % 3
			if no_2 == 1 and no_1 == 0:
				(a[2], a[5], a[8], a[1], a[4], a[7]) = (0, 0, 0, 0, 0, 0)
			elif no == 1:
				for k in range(2, 9, 3):
					if a[k] != 0:
						a[k] -= 1
						break
			elif no == 2:
				if no_1 > 0:
					for k in range(1, 9, 3):
						if a[k] != 0:
							a[k] -= 1
							break
				else:
					j = 2
					i = 2
					while j > 0:
						if a[i] >= j:
							a[i] -= j
							j = 0
						else:
							j -= a[i]
							a[i] = 0
							i += 3
		elif no_2 < no_1:
			no = (no_1 - no_2) % 3
			if no_1 == 1 and no_2 == 0:
				(a[2], a[5], a[8], a[1], a[4], a[7]) = (0, 0, 0, 0, 0, 0)
			elif no == 1:
				for k in range(1, 9, 3):
					if a[k] != 0:
						a[k] -= 1
						break
			elif no == 2:
				if no_2 > 0:
					for k in range(2, 9, 3):
						if a[k] != 0:
							a[k] -= 1
							break
				else:
					j = 2
					i = 1
					while j > 0:
						if a[i] >= j:
							a[i] -= j
							j = 0
						else:
							j -= a[i]
							a[i] = 0
							i += 3
		for i in range(9, -1, -1):
			s += str(i) * a[i]
		if len(s) == 0:
			print(-1)
		else:
			print(int(s))
	t -= 1


n = int(input())
while n > 0:
	num = 0
	t = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	sum1 = sum(a) % 3
	if sum1 == 0:
		flag = 1
	elif sum1 in a and sum1 != 0:
		c = a.index(sum1)
		del a[c]
	elif sum1 + 3 in a:
		c = a.index(sum1 + 3)
		del a[c]
	elif sum1 + 6 in a:
		c = a.index(sum1 + 6)
		del a[c]
	elif sum1 == 1:
		if 2 in a:
			c = a.index(2)
			del a[c]
			if 2 in a:
				c = a.index(2)
				del a[c]
			elif 5 in a:
				c = a.index(5)
				del a[c]
			else:
				c = a.index(8)
				del a[c]
		elif 5 in a:
			c = a.index(5)
			del a[c]
			if 5 in a:
				c = a.index(5)
				del a[c]
			elif 8 in a:
				c = a.index(8)
				del a[c]
		elif 8 in a:
			c = a.index(8)
			del a[c]
			if 8 in a:
				c = a.index(8)
				del a[c]
	elif sum1 == 2:
		if 1 in a:
			c = a.index(1)
			del a[c]
			if 1 in a:
				c = a.index(1)
				del a[c]
			elif 4 in a:
				c = a.index(4)
				del a[c]
			else:
				c = a.index(7)
				del a[c]
		elif 4 in a:
			c = a.index(4)
			del a[c]
			if 4 in a:
				c = a.index(4)
				del a[c]
			elif 7 in a:
				c = a.index(7)
				del a[c]
		elif 7 in a:
			c = a.index(7)
			del a[c]
			if 7 in a:
				c = a.index(7)
				del a[c]
	num = int(''.join(map(str, a)))
	if 0 not in a:
		num = -1
	print(num)
	n -= 1


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	total = sum(x)
	x.sort()
	x.reverse()
	dic = {}
	(b1, b2, b0) = ([], [], [])
	for j in range(n):
		if x[j] != 0:
			if x[j] % 3 == 0:
				b0.append(x[j])
			elif x[j] % 3 == 1:
				b1.append(x[j])
			elif x[j] % 3 == 2:
				b2.append(x[j])
		if x[j] in dic:
			dic[x[j]] += 1
		else:
			dic[x[j]] = 1
	if 0 in dic:
		if total % 3 == 0:
			ans = int(''.join((str(y) for y in x)))
			print(ans)
		elif total % 3 == 1:
			flag = 1
			if len(b1) >= 1:
				x.remove(b1[-1])
			elif len(b2) >= 2:
				x.remove(b2[-1])
				x.remove(b2[-2])
			else:
				flag = 0
			if flag == 1:
				ans = int(''.join((str(y) for y in x)))
				print(ans)
			else:
				print('-1')
		elif total % 3 == 2:
			flag = 1
			if len(b2) >= 1:
				x.remove(b2[-1])
			elif len(b1) >= 2:
				x.remove(b1[-1])
				x.remove(b1[-2])
			else:
				flag = 0
			if flag == 1:
				ans = int(''.join((str(y) for y in x)))
				print(ans)
			else:
				print('-1')
	else:
		print('-1')


def make_div_3(a):
	d = {1: [1, 4, 7], 2: [2, 5, 8]}
	rem = sum(a) % 3
	while rem:
		l1 = d[rem]
		i = sorted(list(set(a).intersection(l1)))
		if i:
			a.remove(i[0])
		else:
			l2 = d[2 if rem == 1 else 1]
			i = sorted(list(set(a).intersection(l2)))
			if i:
				a.remove(i[0])
			else:
				return -1
		rem = sum(a) % 3
	if len(a) == a.count(0):
		return [0]
	return a

def __starting_point():
	t = int(input())
	while t:
		n = int(input())
		a = [int(i) for i in input().split()]
		if not 0 in a:
			print(-1)
		else:
			sa = sorted(a)
			sa.reverse()
			a = make_div_3(sa)
			if a == -1:
				print(a)
			else:
				print(''.join([str(i) for i in a]))
		t -= 1
__starting_point()


def check1(array):
	last = [0 for i in range(10)]
	for i in range(10):
		last[i] = array[i] - array[i] % 3
		array[i] = array[i] % 3
	j = 9
	while j >= 0:
		if j % 3 == 0:
			last[j] += array[j]
		else:
			for i in range(j - 1, 0, -1):
				if (j + i) % 3 == 0:
					while array[j] != 0 and array[i] != 0:
						last[j] += 1
						last[i] += 1
						array[j] -= 1
						array[i] -= 1
		j -= 1
	ans = [str(i) * last[i] for i in range(10)]
	return int(''.join(ans[::-1]))

def check2(array):
	last = [0 for i in range(10)]
	j = 9
	while j >= 0:
		if j % 3 == 0:
			last[j] = array[j]
			array[j] = 0
		else:
			for i in range(j - 1, 0, -1):
				if (j + i) % 3 == 0:
					while array[j] != 0 and array[i] != 0:
						last[j] += 1
						last[i] += 1
						array[j] -= 1
						array[i] -= 1
		j -= 1
	for i in range(10):
		last[i] += array[i] - array[i] % 3
	ans = [str(i) * last[i] for i in range(10)]
	return int(''.join(ans[::-1]))
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	array = [0 for i in range(10)]
	arr = list(map(int, input().strip().split()))
	for j in arr:
		array[j] += 1
	if array[0] == 0:
		print(-1)
	else:
		array1 = array[:]
		a = check1(array)
		b = check2(array1)
		print(max(a, b))


def check1(array):
	last = [0 for i in range(10)]
	last[8] += min(array[8], array[1])
	last[1] = min(array[8], array[1])
	array[1] -= min(array[8], array[1])
	last[7] += min(array[7], array[2])
	last[2] += min(array[7], array[2])
	array[2] -= min(array[7], array[2])
	while array[5] != 0 and array[4] != 0:
		last[5] += 1
		last[4] += 1
		array[5] -= 1
		array[4] -= 1
	while array[5] != 0 and array[1] != 0:
		last[5] += 1
		last[1] += 1
		array[5] -= 1
		array[1] -= 1
	last[4] += min(array[4], array[2])
	last[2] += min(array[4], array[2])
	array[2] -= min(array[4], array[2])
	last[2] += min(array[1], array[2])
	last[1] += min(array[1], array[2])
	temp = array[1]
	array[1] -= min(array[1], array[2])
	array[2] -= min(temp, array[2])
	for i in range(10):
		if i % 3 == 0:
			last[i] += array[i]
		else:
			last[i] += array[i] - array[i] % 3
	ans = [str(i) * last[i] for i in range(10)]
	return int(''.join(ans[::-1]))

def check2(array):
	last = [0 for i in range(10)]
	for i in range(10):
		if i % 3 == 0:
			last[i] += array[i]
		else:
			last[i] += array[i] - array[i] % 3
			array[i] -= last[i]
	last[8] += min(array[8], array[1])
	last[1] += min(array[8], array[1])
	array[1] -= min(array[8], array[1])
	last[7] += min(array[7], array[2])
	last[2] += min(array[7], array[2])
	array[2] -= min(array[7], array[2])
	while array[5] != 0 and array[4] != 0:
		last[5] += 1
		last[4] += 1
		array[5] -= 1
		array[4] -= 1
	while array[5] != 0 and array[1] != 0:
		last[5] += 1
		last[1] += 1
		array[5] -= 1
		array[1] -= 1
	last[4] += min(array[4], array[2])
	last[2] += min(array[4], array[2])
	array[2] -= min(array[4], array[2])
	last[2] += min(array[1], array[2])
	last[1] += min(array[1], array[2])
	temp = array[1]
	array[1] -= min(array[1], array[2])
	array[2] -= min(temp, array[2])
	ans = [str(i) * last[i] for i in range(10)]
	return int(''.join(ans[::-1]))
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	array = [0 for i in range(10)]
	arr = list(map(int, input().strip().split()))
	for j in arr:
		array[j] += 1
	if array[0] == 0:
		print(-1)
	else:
		array1 = array[:]
		a = check1(array)
		b = check2(array1)
		print(max(a, b))


t = int(input())
l1 = [[8, 7], [8, 4], [8, 1], [7, 5], [7, 2], [5, 4], [5, 1], [4, 2], [2, 1]]
l2 = [[8, 5], [8, 2], [7, 4], [7, 1], [5, 8], [5, 2], [4, 7], [4, 1], [2, 8], [2, 5], [1, 7], [1, 4]]
length = 9
while t > 0:
	t -= 1
	d = {}
	d2 = {}
	fin = {}
	n = int(input())
	a = list(map(int, input().split()))
	bol = True
	for k in range(10):
		d[k] = 0
		d2[k] = 0
		fin[k] = 0
	for i in range(n):
		d[a[i]] += 1
		if bol and a[i] == 0:
			bol = False
	if bol:
		print('-1')
	else:
		ans = ''
		for (a, b) in l1:
			z = min(d[a], d[b])
			if z % 2 == 1:
				z -= 1
			fin[a] += z
			fin[b] += z
			d[a] -= z
			d[b] -= z
		for j in range(10):
			if j % 3 != 0:
				d2[j] = d[j] % 3
				d[j] -= d2[j]
		for (a, b) in l2:
			if d2[a] == 2 and d2[b] >= 1:
				d[a] += 2
				d[b] += 1
				d2[a] -= 2
				d2[b] -= 1
		for (a, b) in l1:
			z = min(d2[a], d2[b])
			if z > 0:
				d[a] += z
				d[b] += z
				d2[a] -= z
				d2[b] -= z
		for _ in range(9, -1, -1):
			ans += str(_) * (d[_] + fin[_])
		if ans == '0' * d[0]:
			print(0)
		else:
			print(ans)


test_cases = int(input())
for i in range(0, test_cases):
	num_digits = int(input())
	input_str = input()
	digits_old = input_str.split()
	digits = []
	num_zero = 0
	for num in digits_old:
		if num == '0':
			num_zero += 1
		digits.append(int(num))
	if num_zero == 0:
		print(-1)
	else:
		digits.sort(reverse=True)
		flag = 1
		que0 = []
		que1 = []
		que2 = []
		sum_digits = 0
		for num in digits:
			if num % 3 == 0:
				que0.append(num)
			if num % 3 == 1:
				que1.append(num)
			if num % 3 == 2:
				que2.append(num)
			sum_digits += num
		if sum_digits % 3 == 0:
			number = 0
		elif sum_digits % 3 == 1:
			if len(que1) > 0:
				digits.remove(que1[len(que1) - 1])
			elif len(que2) > 1:
				digits.remove(que2[len(que2) - 1])
				digits.remove(que2[len(que2) - 2])
			else:
				print(-1)
				flag = 0
		elif len(que2) > 0:
			digits.remove(que2[len(que2) - 1])
		elif len(que1) > 1:
			digits.remove(que1[len(que1) - 1])
			digits.remove(que1[len(que1) - 2])
		else:
			print(-1)
			flag = 0
		if flag == 1:
			number = 0
			for num in digits:
				number = number * 10 + num
			print(number)


test_cases = int(input())
for i in range(0, test_cases):
	num_digits = int(input())
	input_str = input()
	digits_old = input_str.split()
	digits = []
	num_zero = 0
	for num in digits_old:
		if num == '0':
			num_zero += 1
		digits.append(int(num))
	if num_zero == 0:
		print(-1)
	else:
		digits.sort(reverse=True)
		start = True
		flag = 1
		while start or number != 0:
			start = False
			number = 0
			sum_digits = 0
			for num in digits:
				sum_digits += num
				number = number * 10 + num
			if sum_digits % 3 == 0:
				print(number)
				flag = 0
				break
			if digits[num_digits - 1 - num_zero] in [0, 3, 6, 9]:
				num_zero += 1
				continue
			del digits[num_digits - 1 - num_zero]
			num_digits -= 1
		if flag == 1:
			print(0)