#P11046. [2016杭电多校]K-wolf Number

    ID: 10188 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-数位 DP状态编码前导零状态上界限制状态非受限状态记忆化预计算转移

[2016杭电多校]K-wolf Number

K-wolf Number

Problem 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≤L≤R≤1e181 \leq L \leq R \leq 1e18 2≤K≤52 \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

Author

ZSTU

Source

2016 Multi-University Training Contest 5