Lottery Tickets

Hyunwoo decided to sell the tickets for this concert tour like lottery tickets. The rule is simple. A fan buys a ticket online and receives a unique reservation number. Numbers are assigned separately for each show, starting at 0 in the order the reservations arrive. A fan whose ticket wins gets into the concert, and a fan whose ticket loses does not.

Hyunwoo draws the winning number at random, but his random number generator is very slow. To call it as few times as possible he came up with a strange yet fair way of drawing the winners.

Once the reservations for a show close, Hyunwoo sets $M$ to the number of reservations and draws one random integer $Z$ from $\{0, \dots, M-1\}$. That is the only call to the generator. He then picks an integer $r > 0$ that decides how hard it is to win.

Here is how $Z$ and $r$ single out the winning tickets.

First, write the reservation numbers $0, \dots, M-1$ and $Z$ as decimal strings of length $n$, where $n$ is the number of digits of $M-1$ written without leading zeros. A number with fewer than $n$ digits is padded with leading zeros so that every string has length $n$.

Let reservation number $A$ be $a_1 \dots a_n$ and let $Z$ be $z_1 \dots z_n$. Ticket $A$ wins if the two strings share a common substring of length at least $r$ starting at the same position, that is, if there is an $i$ with $1 \le i \le n-r+1$ and $z_i \dots z_{i+r-1} = a_i \dots a_{i+r-1}$. For example, when $Z = 56743$ and $r = 3$, ticket $06740$ wins while ticket $56143$ does not.

Given $M$, $Z$ and $r$, write a program that counts the winning tickets.

The first line contains the number of shows $C$. ($1 \le C \le 5000$)

Each of the next $C$ lines contains $M$, $Z$ and $r$ for one show, separated by spaces. ($0 < M \le 10^{18}$, $0 \le Z \le M-1$, $r \ge 1$) The value of $r$ never exceeds the number of digits of $M-1$.

For each show, print the number of winning tickets on its own line.