/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
以下の 2 つの条件を満たす正の整数 n の最小値を求めてください。
- n は K の倍数である。
- n の十進表記には、
0が 2 文字以上連続して現れる。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq K \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 個目のテストケースを意味する。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
K
出力
T 行出力せよ。i 行目には i 個目のテストケースの答えを出力せよ。
入力例 1
3 17 6801 998244353
出力例 1
1003 34005 16970154001
この入力には 3 個のテストケースが含まれています。
1 個目のテストケースにおいて、条件を満たす最小値は 1003\ (= 17 \times 59) です。
2 個目のテストケースにおいて、条件を満たす最小値は 34005\ (= 6801 \times 5) です。なお、20403\ (= 6801 \times 3) は条件を満たしません。
3 個目のテストケースにおいて、条件を満たす最小値は 16970154001\ (= 998244353 \times 17) です。このように、答えが 32 bit 整数に収まらないこともあります。
Score : 300 points
Problem Statement
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,
0appears two or more times consecutively.
T test cases are given; solve each of them.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq K \leq 10^9
- All input values are integers.
Input
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
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 17 6801 998244353
Sample Output 1
1003 34005 16970154001
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.