AT_abc423_g.[ABC423G] Small Multiple 2

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

• $n$ 是 $K$ 的倍数。
• $n$ 的十进制表示中包含 $S$ 作为子串。

给定 $T$ 组测试用例，请分别计算每组的答案。

什么是子串？一个字符串 $S$ 的子串，指的是通过从 $S$ 的开头删除若干个字符和/或从结尾删除若干个字符后剩下的字符串。例如，“ab” 和 “b” 是 “abc” 的子串，但 “ac” 和 “cba” 不是 “abc” 的子串。

输入按如下格式从标准输入给出：

$T$ $\textrm{case}_1$ $\textrm{case}_2$ $\vdots$ $\textrm{case}_T$

其中，$\textrm{case}_i$ 表示第 $i$ 个测试用例，每个用例如下格式：

$K$  $S$

输出 $T$ 行，第 $i$ 行为第 $i$ 个测试用例的答案（$1 \leq i \leq T$）。

样例解释 1

第一个测试用例中，所有是 $271$ 的正整数倍且十进制表示包含 “414” 的最小值是 $34146$。

第二个测试用例中，所有是 $15$ 的正整数倍且十进制表示包含 “23” 的最小值是 $1230$。

第三个测试用例中，所有是 $155521$ 的正整数倍且十进制表示包含 “1000” 的最小值是 $100000003$。

第四个测试用例中，所有是 $920950937$ 的正整数倍且十进制表示包含 “999999999999999999999” 的最小值是 $1000000999999999999999999999$。

数据范围

• $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$。

由 ChatGPT 5 翻译