题目

有一种特殊的运算X，它的运算方式如下：

对于一个整数n，对它的每一位d，用d+1替换d。

例如，对于193，它的每一位+1后的结果为2，10，4。所以，193的X运算结果为2104。

因为结果可能超过整形范围，所以结果模 10^9+7 的余数即可。

输入格式

第一行一个数字t，代表有t个测试用例。(1<=t<=2*10^5)

接下来t行，每行两个数字，分别代表n和m。(1<=n<=10^9, 1<=m<=2*10^5)

输出格式

t行，每行1个整数，表示对n进行m次运算X后得到的结果的位数模10^9+7的余数。

样例输入

5

1912 1

5 6

999 1

88 2

12 100

样例输出

5

2

6

4

2115

样例解释

对于第一个样例，1912进行一次X运算后得到的结果为21023，长度为5位。

对于第二个样例，5进行6次X运算后得到的结果为21，长度为2位。

对于第三个样例，999进行1次X运算后得到的结果为101010，长度为6。

<