C. Magical Rearrangement
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

HoshiYo is a magician. He specializes in using magic, but he is not good at math. In the math class of the magic school, HoshiYo learns about integers. He suddenly finds something interesting: with his powerful magic, he can change an integer by rearranging its digits.

Formally, for each digit from $$$0$$$ to $$$9$$$, the number of digits $$$i$$$ is $$$a_i$$$. HoshiYo wants to get an integer that meets the following rules:

  • All the given digits are used.
  • There is no leading zero except for $$$0$$$ itself.
  • Adjacent digits cannot be the same.

HoshiYo wonders what's the minimum integer he can get with these digits.

Input

The first line of each test case contains an integer $$$T$$$ ($$$1\le T\le 10^4$$$), indicating the number of test cases.

Each test case contains $$$10$$$ integers $$$a_0,a_1,\ldots ,a_9$$$ ($$$0\le a_i\le 10^5$$$), indicating the number of different digits. Let $$$n=\sum_{i=0}^9a_i$$$. It's guaranteed that $$$1 \le n \le 10^5$$$.

It's also guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$10^5$$$.

Output

For each test case, output the minimum integer HoshiYo can get in a single line. If there's no solution, output $$$-1$$$ in a single line.

Example
Input
3
0 0 1 0 0 0 0 0 0 2
2 0 1 0 0 1 0 2 0 0
3 0 1 0 0 0 0 0 0 0
Output
929
205707
-1