给你一个整数$$$n$$$。您必须对其应用 $$$m$$$ 操作。
在一次操作中,您必须将数字 $$$d$$$ 的每一位数字替换为整数 $$$d + 1$$$ 的十进制表示形式。例如,$$$1912$$$ 在应用一次操作后变为 $$$21023$$$。
在应用 $$$m$$$ 操作后,您必须找到 $$$n$$$ 的长度。由于答案可能非常大,因此打印它对 $$$10^9+7$$$ 取模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。
每个测试用例的唯一行包含两个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$) 和 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) – 初始数量和操作数量。
输出
对于每个测试用例,输出结果数字的长度模$$$10^9+7$$$。
示例
输入 #1
5 1912 1 5 6 999 1 88 2 12 100
输出 #1
5 2 6 4 2115
注意
对于第一个测试,在长度为 $$$5$$$ 的 $$$1$$$ 操作之后,$$$1912$$$ 变为 $$$21023$$$。
对于第二个测试,在长度为 $$$2$$$ 的 $$$6$$$ 操作之后,$$$5$$$ 变为 $$$21$$$。
对于第三个测试,在长度为 $$$6$$$ 的 $$$1$$$ 操作之后,$$$999$$$ 变为 $$$101010$$$。
对于第四个测试,在长度为 $$$4$$$ 的 $$$2$$$ 操作之后,$$$88$$$ 变为 $$$1010$$$。