题目描述

在寒假闲下来的时候，呼和同学研究起数学问题。还给数学起了一个奇怪的外号

呼和同学 对数字有着独到的见解，他认为一个数是呼和数当且仅当这个数的相邻两位都不相同。

例如 12345、12121是呼和数，而 123321、11不是呼和数。

现在呼和同学想知道，对于所有满足以下条件的数中，最小的那个数是什么？如果不存在这样的呼和数，则输出 -1 。

• 对于 $i(0\le i\le 9)$，这个数中是 $i$ 的位数一共有 $a_i$ 个。
• 这个数不能有前导 $0$ ，即 012 是不合法的。

有多组测试点，每组测试点现在给你 $a_0\sim a_9$ ，请你回答呼和同学的问题。

输入格式

第一行包含一个整数 $T$ 。

接下来 $T$ 行，每行 $10$ 个整数，$a_0\sim a_9$ ，含义如题。

输出格式

输出 $T$ ，每行一个整数，表示答案。

样例

输入

5
5 0 0 0 0 0 0 0 0 5
6 0 0 0 0 0 0 0 0 5
0 1 0 2 0 0 0 0 0 0
3 0 0 0 2 0 0 1 0 0 
0 1 2 3 4 5 6 7 8 9

输出

9090909090
-1
313
404070
123234345454565656767676787897979898989898989

数据范围

对于 $100\%$ 的数据，保证：$T\le 10,1 \leq n,a_i\le 10^5$，其中 $n=\sum_{i=0}^9a_i$ 。

$\text{A}:$ 保证最多只有 $2$ 个 $a_i>0$ 。

$\text{B}:$ 保证最多只有 $3$ 个 $a_i>0$ 。