C. Add One
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. You have to apply $$$m$$$ operations to it.

In a single operation, you must replace every digit $$$d$$$ of the number with the decimal representation of integer $$$d + 1$$$. For example, $$$1912$$$ becomes $$$21023$$$ after applying the operation once.

You have to find the length of $$$n$$$ after applying $$$m$$$ operations. Since the answer can be very large, print it modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

The only line of each test case contains two integers $$$n$$$ ($$$1 \le n \le 10^9$$$) and $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the initial number and the number of operations.

Output

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

Example
Input
5
1912 1
5 6
999 1
88 2
12 100
Output
5
2
6
4
2115
Note

For the first test, $$$1912$$$ becomes $$$21023$$$ after $$$1$$$ operation which is of length $$$5$$$.

For the second test, $$$5$$$ becomes $$$21$$$ after $$$6$$$ operations which is of length $$$2$$$.

For the third test, $$$999$$$ becomes $$$101010$$$ after $$$1$$$ operation which is of length $$$6$$$.

For the fourth test, $$$88$$$ becomes $$$1010$$$ after $$$2$$$ operations which is of length $$$4$$$.