AT_arc224_a.Attach 00

Find the minimum value of a positive integer $n$ satisfying the following two conditions.

• $n$ is a multiple of $K$.
• In the decimal representation of $n$, 0 appears two or more times consecutively.

$T$ test cases are given; solve each of them.

求满足以下两个条件的最小正整数 $n$：

• $n$ 是 $K$ 的倍数；
• $n$ 的十进制表示中，数字 0 至少连续出现两次。

共给出 $T$ 组测试用例，请对每组用例求解。

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case:

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$K$

输入从标准输入给出，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例：

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$K$

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

Sample 1 Explanation:
This input contains three test cases.

For the first test case, the minimum value satisfying the conditions is $1003\ (= 17 \times 59)$.

For the second test case, the minimum value satisfying the conditions is $34005\ (= 6801 \times 5)$. Note that $20403\ (= 6801 \times 3)$ does not satisfy the condition.

For the third test case, the minimum value satisfying the conditions is $16970154001\ (= 998244353 \times 17)$. As this shows, the answer may not fit in a $32$-bit integer.

Constraints

• $1 \leq T \leq 10^5$
• $1 \leq K \leq 10^9$
• All input values are integers.

样例 1 解释：
该输入包含三个测试用例。

对于第一个测试用例，满足条件的最小值为 $1003\ (= 17 \times 59)$。

对于第二个测试用例，满足条件的最小值为 $34005\ (= 6801 \times 5)$。注意，$20403\ (= 6801 \times 3)$ 不满足条件。

对于第三个测试用例，满足条件的最小值为 $16970154001\ (= 998244353 \times 17)$。如本例所示，答案可能无法用 32 位整数表示。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq K \leq 10^9$
• 所有输入值均为整数。