题目描述

所谓 k-奇偶差值数，指一个正整数，满足所有偶数位上数字之和减所有奇数位上数字之和的差值为给定数字 $k$ 。（我们认为个位为第$1$位，十位为第$2$位，以此类推...）

现给定三个正整数 $l,r,k$ ，请你求出在 $[l,r]$ 范围内有多少个 k-奇偶差值数。

例如，当$l=100，r=1000，k=6$时，共有 $6$ 个 6-奇偶差值数，分别是：$170,181,280,192,291,390$

输入格式

输入共一行，三个正整数分别表示 $l,r,k$

输出格式

输出共一行，表示满足条件的k-奇偶差值数个数。

100 1000 6

6

1 10 5

0

数据范围

对于$50\%$的数据，$1 \leq l \leq r \leq 10^6$ 对于$100\%$的数据，$1 \leq l \leq r \leq 10^{13}$,$1 \leq k \leq 70$