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 |