C. Add One

Description

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\).

standard input

5
1 0
5 2
6 6
2 1
6 1

standard output

1 
2 4 1 5 3 
-1
-1
1 3 6 5 4 2

Note

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.