The concert promoters of the Bon Jovi Tour 2013 have decided to sell tickets for the concerts in lotteries. The rules are quite simple. For every concert, fans can apply online for tickets. In response they receive unique reservation numbers. It is important that for each concert the numbers distributed online are consecutive nonnegative integers starting with 0. Unfortunately, as the organizers tried to draw reservation numbers randomly, they discovered that the pseudo random generator they used is extremely slow. To minimize the number of calls to the generator, they invented a peculiar but fair enough way to distribute tickets.

As soon as the reservation for a concert is finished, the organizers ascertain the number of submissions M and draw one random integer Z from {0, ..., M - 1} (remember, fans get integers from 0 to M - 1). Integer Z is the only object the organizers have to draw randomly! Finally, to complete the selection rules the organizers determine an integer r > 0 which has a direct impact on the number of selected tickets.

Now, using Z and r, tickets are selected deterministically as follows. For the reservation numbers 0, ..., M - 1 and the number Z, their decimal representations of length n are considered, where n is the length of the representation of M - 1 without leading zeros. Thus, the decimal representations of the remaining numbers are padded on the left with leading zeros, if needed. If z1 ... zn denotes such a representation for Z, then the holder of a number a1 ... an gets the ticket if and only if the strings z1 ... zn and a1 ... an have a common contiguous substring of length r or more which starts at the same position. Speaking formally, he or she gets the ticket if there exists an index i, with 1 ≤ i ≤ n - r + 1, such that zi ... zi+r-1 = ai ... ai+r-1. For example, if Z = 56743 and r = 3 then a fan with a reservation number 06740 gets a ticket, but a fan having 56143 does not.

Your task is to help the organizers to estimate, for given numbers M, Z and r, the exact number of tickets selected in such a way.

Input

The first line contains the number of concerts C (1 ≤ C ≤ 5000). Then follow C lines, each containing three integers M, Z and r (0 < M ≤ 1018, 0 ≤ Z ≤ M - 1 and r ≥ 1). You may safely assume that r is smaller or equal to the length of the decimal representation of M - 1.

Output

For each concert, print one line containing the number of tickets selected during the ticket draw.