AOJ 5162 - K-wolf Number

K-wolf Number

Time Limit: 3000ms

Memory Limit: 65536KB

This problem will be judged on HDU. Original ID: 5787
64-bit integer IO format: %I64d Java class name: Main

Submit Status Statistics

Font Size:

Description

Alice thinks an integer x is a K-wolf number, if every K adjacent digits in decimal representation of x is pairwised different.
Given (L,R,K), please count how many K-wolf numbers in range of [L,R].

Input

The input contains multiple test cases. There are about 10 test cases.

Each test case contains three integers L, R and K.

$1 \leq L \leq R \leq 1e18$
$2 \leq K \leq 5$

Output

For each test case output a line contains an integer.

Sample Input

1 1 2
20 100 5

Sample Output

1
72

Source

2016 Multi-University Training Contest 5