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 ≤ 10³). The next line contains n integers a₁, a₂, ... a_n (a_i = 0 or a_i = 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