题目描述

小杨正在给一些正整数编号。对于一个正整数，将它每一位上的数字相加，得到它的数位和。如果一个正整数的十进制表示中至少出现一次数字 $t$，并且它的数位和能够被 $k$ 整除，则称这个数为“标记数”。给定 $n$、$k$、$t$，请统计 $1$ 到 $n$ 中共有多少个标记数。

输入格式

输入一行，包含三个整数 $n$、$k$、$t$，含义如题目描述所示。

输出格式

输出一个整数，表示 $1$ 到 $n$ 中标记数的个数。

样例

30 3 2

4

105 5 0

2

样例解释

样例 $1$ 中，满足条件的数为 $12$、$21$、$24$、$27$，共 $4$ 个。

样例 $2$ 中，$50$ 的数位和为 $5$，$104$ 的数位和为 $5$，且都含有数字 $0$，因此输出为 $2$。

数据范围

对于全部测试数据，$1 \le n \le 100000$，$1 \le k \le 9$，$0 \le t \le 9$。