← 返回题目列表

AtCoder · abc423_g

G. 小倍数2

中文机器翻译题面 查看原题

分数: 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.