An integer is said to be k-reachable from another integer if the latter can be converted to the former by replacing atmost k digits. Note that, leading 0's are not considered the part of the number and hence are not allowed to replaced with non-zero integers.

For example,

1123 is 15-reachable from 2223 but not 1-reachable.

6 is 2-reachable from 10, but 10 is not 2-reachable from 6

Mancunian has been given the following problem. He is provided the initial integer N and the value of k. Now he has to answer Q queries. Each query is represented by a pair (L, R). The answer for a query is the number of integers in the range L to R (inclusive) which are k-reachable from N.

Input:
The first line contains three integers N, k and Q.
Each of the next Q lines is of the form L R denoting a specific query.

Output:
For each query, output the answer to the given query in a new line.

Constraints:
1 <= N < 10⁷
1 <= k <= 5
1 <= Q <= 10⁵
1 <= L <= R < 10⁷