Problem Description
Xnozero is very interested in k-divide number.
A way of k-divide on a number is defined as if number N can be divide into two parts m, n, and the sum of m and n can be divided by k, then this is a way of k-divide number based k.
For example, 3 + 33 = 36 is a way of 3-divide on number 333, as you can only divide 333 into 3 and 33, and the sum of 3 and 33 is 36, which can be divided by 3.
Zero's number is defined as f(n,k), and f(n,k) is the number of ways of n divided into k-divide numbers.
As defined above, 333 can be divided into two parts in two ways 3|33 and 33|3, so f(333,3)=2.
Now give you A, B, K, can you help Xnozero compute the sum of f(i,K) (A≤i≤B)? (1 ≤ K ≤ 20, 10 ≤ A ≤ B ≤ 1017)
Input
Multiple cases, process to the end of file.
Each line contains 3 integers A,B,K as descripted above.
Output
Output the sum of f(i,k), one per line.
Sample Input
333 333 3
10 100 2
Sample Output
2
46
