Problem Statement

Print one integer $X$ that satisfies all of the following conditions.

• $1 \leq X \leq 10^{18}$
• $X$ is a multiple of $M$.
• For each $i \ (1 \leq i \leq 9)$, the decimal representation of $X$ contains the digit $i$ at least $d_i$ times.

If there are multiple $X$ satisfying the conditions, you may print any of them. It can also be proved that, under the constraints of this problem, an $X$ satisfying the conditions always exists.

You are given $T$ test cases; answer each of them.

Constraints

• All input values are integers.
• $1 \leq T \leq 10^4$
• $1 \leq M \leq 10^9$
• $d_i \geq 0 \ (1 \leq i \leq 9)$
• $d_1 + d_2 + \dots + d_9 \leq 9$

Input

The input is given from Standard Input in the following format, where $case_i$ represents the $i$-th test case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each case is given in the following format.

$M$
$d_1$ $d_2$ $d_3$ $d_4$ $d_5$ $d_6$ $d_7$ $d_8$ $d_9$

Output

Print $T$ lines. On the $i$-th line, print one integer $X$ satisfying the conditions for the $i$-th test case.

Sample

3
7
1 0 0 1 0 0 0 0 0
1
0 0 0 0 0 0 0 0 9
998244353
0 1 2 2 1 0 0 1 2

14
909090909090909090
998244353