JULIUS3 - Julius Divisibility

To further test his sons, Julius' now got n cards, each card contains either digit 0, or digit 5. Julius ask the princes to choose several cards and put them in a line so that they get some number. What is the largest possible number they can make from the cards this is divisible by 90?

Princes must make the number without leading zero. They doesn't have to use all the cards.

Input

The first line contains test cases t (1 <= t <= 100), the next line contains integer n (1 ≤ n ≤ 103). The next line contains n integers a1, a2, ... an (ai = 0 or ai = 5).

Output

In t lines print the maximum number divisible by 90. If they can't make any number divisible by 90 print -1.

Example

Input:
2
4
5 0 5 0
11
5 5 5 5 5 5 5 5 0 5 5

Output:
0
5555555550

Added by:`Ak
Date:2014-12-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.