给定一个整数 $n$。你需要对它做 $m$ 次操作。在一次操作中，你要将这个数的每一位 $d$ 替换成 $d + 1$。比如，$1912$ 在进行一次操作后将变成 $21023$。

请求出整数 $n$ 进行了 $m$ 次操作后的长度。答案可能很大，输出对 $10^9+7$ 取模后的结果。

输入格式

​ 第一行一个整数 $t$，表示测试单元的个数。

​ 接下来 $t$ 行，每行有两个整数 $n$ 和 $m$，表示最初的数字和进行多少次操作。

输出格式

​ 对于每个测试单元输出最终数字的长度，答案对 $10^9 + 7$ 取模。

样例输入

5
1912 1
5 6
999 1
88 2
12 100

样例输出

5
2
6
4
2115

数据规模

​ 所有数据保证 $1\leq t \leq 2⋅10^5$，$1 \leq n \leq 10^9$，$1\leq m \leq 2⋅10^5$。