题目描述

对于一个整数，对其进行一次 按位扩展 操作，能够让其每一位上的数字都增加 $1$。也就是说，如果这个十进制整数当前某位上是 $d$，则进行一次按位扩展操作后这一位上的数字会变成 $d+1$；特别地，若这一位上的数字是 $9$，则进行一次按位扩展后会变成两位数字 $10$。比如：

• 对整数 $123$ 进行一次按位扩展操作后它将变为 $234$；
• 对整数 $929$ 进行一次按位扩展操作后它将变为 $10310$；
• 对整数 $1993$ 进行一次按位扩展操作后它将变为 $210104$。

现在给你两个整数 $n$ 和 $m$（$1 \le n \le 10^9; 1 \le m \le 2 \cdot 10^5$）。

求：对十进制整数 $n$ 进行连续 $m$ 次按位扩展操作后，$n$ 有多少位？由于最终的 $n$ 的位数可能非常大，所以你只需要输出最终 $n$ 的位数模 $10^9 + 7$ 的结果即可。

输入格式

输入包含多组测试数据。

输入的第一行包含一个整数 $t(1 \le t \le 2 \cdot 10^5)$，表示测试数据组数。

接下来每组测试数据占一行，包含两个整数 $n$ 和 $m$，以一个空格分隔（$1 \le n \le 10^9; 1 \le m \le 2 \cdot 10^5$）。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示对整数 $n$ 进行连续 $m$ 次按位扩展操作后它对应的十进制整数的位数模 $10^9 + 7$ 的结果。

5
1993 1
5 6
999 1
88 2
18 30

6
2
6
4
20

说明/提示

样例解释

• 第1组测试数据：对 $1993$ 进行 $1$ 次按位扩展操作后它将变为 $210104$，占 $6$ 位；
• 第2组测试数据：对 $5$ 进行 $6$ 次按位扩展操作后它将变为 $21$，占 $2$ 位；
• 第3组测试数据：对 $999$ 进行 $1$ 次按位扩展操作后它将变为 $101010$，占 $6$ 位 ；
• 第4组测试数据：对 $88$ 进行 $2$ 次按位扩展操作后它将变为 $1010$，占 $4$ 位；
• 第5组测试数据：对 $18$ 进行 $30$ 次按位扩展操作后它将变为 $43323221211010910998$，占 $20$ 位。

数据规模与约定

• 对于 $30\%$ 的数据，$t \le 20; n \le 10^3; m \le 20$
• 对于 $60\%$ 的数据，$t \le 2000; n \le 10^6; m \le 2000$
• 对于 $100\%$ 的数据，$1 \le t \le 2 \cdot 10^5; 1 \le n \le 10^9; 1 \le m \le 2 \cdot 10^5$