你拥有一个数字 $X$。魔鬼想要这个数字的一份份额。他会取走其中长度为 $K$ 的最大子数。请通过重新排列数字 $X$ 中的各位数字，使得魔鬼得到的份额最小。

形式化地，你有 $S$ ($1 \le S \le 100\,000$) 个介于 $1$ 到 $9$ 之间的数字可供使用。给定一个整数 $K$ ($1 \le K \le S$)，你需要使用所有可用的数字构造一个数字 $X$，使得 $X$ 中长度为 $K$ 的最大子串尽可能小。

说明：长度为 $K$ 的子串是指由 $X$ 中 $K$ 个连续数字按原顺序组成的十进制整数。在数字 $X$ 中共有 $S - K + 1$ 个这样的子串。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100\,000$)，表示需要分析的测试场景数量。

接下来是 $T$ 个测试场景的描述。每个测试场景包含两行：

第一行包含一个整数 $K$，表示要考虑的子串长度。

第二行包含 $9$ 个空格分隔的整数：$D_1, D_2, \dots, D_9$，其中 $D_i$ 表示你拥有的数字 $i$ 的个数。($0 \le D_i$, $D_1 + D_2 + \dots + D_9 = S$)。

所有测试场景的 $S$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试场景，在单独的一行中打印你构造的数字 $X$。

如果存在多个具有相同最小可能长度 $K$ 子串的数字 $X$，你可以输出其中任意一个。

子任务

(1) $0 \le D_1, D_2, D_3, D_4 \le 3$, $D_5 = D_6 = \dots = D_9 = 0$, $1 \le T \le 1536$，场景不重复 (13 分)

(2) $K = 2$ (14 分)

(3) $D_3 = D_4 = \dots = D_9 = 0$ (29 分)

(4) 无附加限制 (44 分)

样例

样例输入 1

3
2
1 1 2 0 0 0 0 0 0
7
2 4 2 0 0 6 2 2 2
7
3 3 3 0 0 6 2 2 2

样例输出 1

2313
62616236261623778899
623616236162361778899

说明

样例中有三个测试场景需要考虑。

在第一个场景中，$K = 2$，你需要排列数字 $1233$。 一个最优的 $X$ 是 $2313$，其长度为 $2$ 的子串为：$23, 31$ 和 $13$，其中最大的是 $31$。没有其他 $X$ 能得到更小的长度为 $2$ 的最大子串。 另一个最优的 $X$ 是 $3123$，因为其长度为 $2$ 的最大子串也是 $31$。

在第二个场景中，$K = 7$，你需要排列数字 $11222233666666778899$。 一个最优的 $X$ 是 $62616236261623778899$，其长度为 $7$ 的最大子串是 $6261623$。

在第三个场景中，$K = 7$，你需要排列数字 $111222333666666778899$。 一个最优的 $X$ 是 $623616236162361778899$，其长度为 $7$ 的最大子串是 $6236177$。