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: interview

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)

def qsort(inlist):
 if inlist == []: 
  return []
 else:
  pivot = inlist[0]
  lesser = qsort([x for x in inlist[1:] if x < pivot])
  greater = qsort([x for x in inlist[1:] if x >= pivot])
  return lesser + [pivot] + greater
def mul3(ip):   
 q0=[]
 q1=[]
 q2=[]
 qsort(ip)
 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)

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 

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 = 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(s)
 t -= 1

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_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(s)
 t -= 1

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_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 
   else:
    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 
   else:
    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

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")

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:
   print(''.join(str(y) for y in x))
  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:
    print(''.join(str(y) for y in x))
   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:
    print(''.join(str(y) for y in x))
   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)


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 = {}
 n = int(input())
 a = list(map(int,input().split()))
 bol = True
 for k in range(10) :
  d[k] = 0
  d2[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 j in range(10) :
   if j % 3 != 0 :
    d2[j] = d[j]%3
    d[j] -= d2[j]
  for a,b in l1 :
   z = min(d2[a],d2[b])
   if z == 2 :
    d[a] += z
    d[b] += z
    d2[a] -= z
    d2[b] -= z

  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[_]
  if ans == '0'*d[0] :
   print(0)
  else :
   print(ans)


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 = {}
 n = int(input())
 a = list(map(int,input().split()))
 bol = True
 for k in range(10) :
  d[k] = 0
  d2[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 j in range(10) :
   if j % 3 != 0 :
    d2[j] = d[j]%3
    d[j] -= d2[j]
  for a,b in l1 :
   z = min(d2[a],d2[b])
   if z == 2 :
    d[a] += z
    d[b] += z
    d2[a] -= z
    d2[b] -= z

  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[_]
  print(ans)


# your code goes here
# your code goes here
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
  else:
   if 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)

# your code goes here
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)