Plus One

Problem Description

You are given an integer $n$. You need to perform $m$ operations on it. In one operation, you replace every digit $d$ with $d + 1$. For example, $1912$ becomes $21023$ after one operation.

Find the length of the number after $n$ has been operated on $m$ times. The answer may be large; output it modulo $10^9+7$.

Input Format

The first line contains an integer $t$, the number of test cases.

Each of the next $t$ lines contains two integers $n$ and $m$, denoting the initial number and the number of operations.

Output Format

For each test case, output the length of the final number, modulo $10^9 + 7$.

Sample Input

5
1912 1
5 6
999 1
88 2
12 100

Sample Output

5
2
6
4
2115

Constraints

For all data, $1\leq t \leq 2\cdot 10^5$, $1 \leq n \leq 10^9$, $1\leq m \leq 2\cdot 10^5$.