分数: 600 点
问题陈述
找到正整数的最小可能值 n 满足以下两个条件:
- n 是的倍数 K.
- 的十进制表示 n 包含 S 作为子字符串。
T 给出了测试用例,因此请找到每个测试用例的答案。
什么是子串?
字符串的子字符串 S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S。 例如,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
在第一个测试用例中,在是 的倍数的正整数中 271,其十进制表示形式包含的最小值 414 作为子字符串是 34146.
在第二个测试用例中,在是 的倍数的正整数中 15,其十进制表示形式包含的最小值 23 作为子字符串是 1230.
在第三个测试用例中,在是 的倍数的正整数中 155521,其十进制表示形式包含的最小值 1000 作为子字符串是 100000003.
在第四个测试用例中,在是 的倍数的正整数中 920950937,其十进制表示形式包含的最小值 999999999999999999999 作为子字符串是 1000000999999999999999999999.