还记得小学时玩的拍手游戏吗？这里有一个更难的版本。

给定两个正整数 $n$ 和 $m$。请找到最小的整数 $x$，使得 $x > n$ 且 $x$ 是一个“好数”。一个好数 $x$ 满足 $x \equiv 0 \pmod{m}$ 或者 $x$ 的十进制表示中包含 $m$ 作为子串。

例如，当 $m = 3$ 且 $n = 7$ 时，$x = 9$ 是答案，因为 $9 \equiv 0 \pmod{3}$。当 $m = 3$ 且 $n = 12$ 时，$x = 13$ 是答案，因为 $13$ 包含 $3$ 作为子串。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，一行包含两个整数 $n$ 和 $m$ ($1 \le n < 10^{10^6}, 1 \le m \le 10^9$)。$n$ 不包含前导零。

保证 $\sum \lfloor \log_{10}(n) \rfloor \le 3 \times 10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数 $x$，表示答案。

样例

样例输入 1

6
7 3
12 3
9 10
249 51
1369 37
2 1

样例输出 1

9
13
10
251
1370
3