Background

This is the fourth time that Little R and Little Z have played the counting-off game, so they decided not to write a long problem statement anymore. You only need to know that they came up with another strange counting rule, and they want to figure out which numbers can be called out.

Problem Description

For any positive integer $n$, define the function $f(n)$ as the sum of all digits of $n$ in decimal. For example, $f(114514)=1+1+4+5+1+4=16$. Clearly, $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,k$, define $g(n,k)=f(f(...f(n)))$ (with a total of $k$ layers of $f$).

To make the counting-off game different each round, Little R and Little Z decide to set two positive integers $k,m$ for each round, and specify that: in this round, all positive integers $n$ satisfying $g(n,k)=m$ cannot be called out.

Since both of them are skilled players, to prevent the game from going on forever, each round also gives a positive integer $N$ as the upper bound of counting off. They want to know: among the positive integers not exceeding $N$, how many cannot be called out under this rule.

Input Format

The first line contains a positive integer $T$, indicating the number of game rounds played by Little R and Little Z. It is guaranteed that $1 \le T \le 5$.

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

Output Format

Output $T$ lines. Each line contains one integer, representing the number of integers that cannot be called out in this round, modulo $10^9+7$.

2
114 1 5
514 2 10

8
10

Hint

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

Translated by ChatGPT 5