Background

This is the fourth time Little R and Little Z are playing the number-calling game, so they decided not to write a long problem statement. You only need to know that they have invented a strange rule for calling numbers and want to calculate which numbers can be called.

For any positive integer $n$, define the function $f(n)$ as the sum of the digits of $n$ in decimal representation. For example, $f(114514)=1+1+4+5+1+4=16$. Obviously, $f(n)$ is also a positive integer, so we can consider nested applications such as $f(f(n)), f(f(f(n)))$, and so on. Furthermore, for positive integers $n$ and $k$, we can define $g(n, k) = f(f(\dots f(n)))$ (with $k$ layers of $f$).

To ensure that the number-calling game is not the same every round, Little R and Little Z decide to set two positive integers $k$ and $m$ for each round, and stipulate that in this round, all positive integers $n$ satisfying $g(n, k) = m$ cannot be called.

Since both are experts at the game, to prevent the game from continuing indefinitely, each round provides a positive integer $N$ representing the upper bound for the numbers. They want to know: among all positive integers not exceeding $N$, how many cannot be called according to this rule?

Input

Read data from standard input.

The first line contains a positive integer $T$, representing the number of rounds of the game played by Little R and Little Z, with $1 \le T \le 5$.

The next $T$ lines each contain three positive integers $N, k, m$, describing a round of the game as defined above. It is guaranteed that $1 \le N \le 10^{1000}$ and $1 \le k, m \le 10^9$.

Output

Output to standard output.

Output $T$ lines, each containing an integer representing the number of integers that cannot be called in that round, modulo $10^9+7$.

Examples

Input 1

2
114 1 5
514 2 10

Output 1

8
10

Note

In the first round, the numbers that cannot be called are $5, 14, 23, 32, 41, 50, 104, 113$.