HoshiYo 是一位魔术师。他擅长使用魔法，但不擅长数学。在魔法学校的数学课上，HoshiYo 学习了关于整数的知识。他突然发现了一件有趣的事情：利用他强大的魔法，他可以通过重新排列数字来改变一个整数。

形式化地，对于从 0 到 9 的每个数字，数字 $i$ 的个数为 $a_i$。HoshiYo 想要得到一个满足以下规则的整数：

• 必须使用所有给定的数字。
• 除了数字 0 本身外，不能有前导零。
• 相邻的数字不能相同。

HoshiYo 想知道他能用这些数字得到的最小整数是多少。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 每个测试用例包含 10 个整数 $a_0, a_1, \dots, a_9$ ($0 \le a_i \le 10^5$)，表示不同数字的个数。 令 $n = \sum_{i=0}^9 a_i$。保证 $1 \le n \le 10^5$。 同时保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出 HoshiYo 能得到的最小整数，占一行。如果没有解，则输出 $-1$。

样例

输入 1

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

输出 1

929
205707
-1