/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
以下の 2 つの条件を満たす正の整数 n としてあり得る最小値を求めてください。
- n は K の倍数である。
- n の十進法での表記には、部分文字列として S が含まれる。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
部分文字列とは
ある文字列 S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab や b は abc の部分文字列ですが、ac や cba は abc の部分文字列ではありません。
制約
- T は整数。
- 1 \leq T \leq 200
- K は整数。
- 1 \leq K \leq 10^9
- S は数字 (
0-9) からなる文字列。 - S の先頭の文字は
0でない。 - 1 \leq |S| \leq 5 \times 10^5
- すべてのテストケースの |S| の総和は 5 \times 10^5 以下である。
入力
入力は以下の形式で標準入力から与えられる。
T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T
\textrm{case}_i は i 番目のテストケースを表す。各テストケースは以下の形式で与えられる。
K S
出力
T 行出力せよ。i 行目 (1 \leq i \leq T) には i 番目のテストケースに対する答えを出力せよ。
入力例 1
4 271 414 15 23 155521 1000 920950937 999999999999999999999
出力例 1
34146 1230 100000003 1000000999999999999999999999
1 番目のテストケースにおいて、271 の倍数である正の整数のうち、十進法での表記に部分文字列として 414 を含むものの最小値は 34146 です。
2 番目のテストケースにおいて、15 の倍数である正の整数のうち、十進法での表記に部分文字列として 23 を含むものの最小値は 1230 です。
3 番目のテストケースにおいて、155521 の倍数である正の整数のうち、十進法での表記に部分文字列として 1000 を含むものの最小値は 100000003 です。
4 番目のテストケースにおいて、920950937 の倍数である正の整数のうち、十進法での表記に部分文字列として 999999999999999999999 を含むものの最小値は 1000000999999999999999999999 です。
Score : 600 points
Problem Statement
Find the minimum possible value of a positive integer n that satisfies the following two conditions:
- n is a multiple of K.
- The decimal representation of n contains S as a substring.
T test cases are given, so find the answer for each.
What is a substring?
A substring of a string S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example,ab and b are substrings of abc, but ac and cba are not substrings of abc.
Constraints
- T is an integer.
- 1 \leq T \leq 200
- K is an integer.
- 1 \leq K \leq 10^9
- S is a string consisting of digits (
0-9). - The first character of S is not
0. - 1 \leq |S| \leq 5 \times 10^5
- For each input file, the sum of |S| over all test cases is at most 5 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T
\textrm{case}_i represents the i-th test case. Each test case is given in the following format:
K S
Output
Output T lines. The i-th line (1 \leq i \leq T) should contain the answer to the i-th test case.
Sample Input 1
4 271 414 15 23 155521 1000 920950937 999999999999999999999
Sample Output 1
34146 1230 100000003 1000000999999999999999999999
In the first test case, among positive integers that are multiples of 271, the minimum one whose decimal representation contains 414 as a substring is 34146.
In the second test case, among positive integers that are multiples of 15, the minimum one whose decimal representation contains 23 as a substring is 1230.
In the third test case, among positive integers that are multiples of 155521, the minimum one whose decimal representation contains 1000 as a substring is 100000003.
In the fourth test case, among positive integers that are multiples of 920950937, the minimum one whose decimal representation contains 999999999999999999999 as a substring is 1000000999999999999999999999.