[信息与未来 2016] 幸运数字(Lucky Numbers)

小明认为，如果以下条件之一成立，则正整数 $x$ 就是一个幸运数字：

例如， $105$ （ $7$ 的倍数）、 $442$ （包含44）、 $1284$ （ $4$ 的倍数）都是幸运数字，而 $474$ 则不是。编程统计 $1$ 到 $n$ 中幸运数字的数量。

一行，一个整数 $n$ 。

一行，一个整数， $1,2,3,\dots n$ 中幸运数字的数量。

对于 $100\%$ 的数据， $1\le n\leq 10^6$ 。

本题原始满分为 $10\text{pts}$ 。

本题涉及的知识点从属于 GESP 3级，难度（CF Rating）：850。

Subtask	分值	测试点编号	说明
0	10	1~2	样例及最小边界测试
1	20	3~8	$1 \le n \le 1000$
2	15	9~11	Hack 数据： $n = 1$ （答案 $0$ ）、 $n = 44$ 、 $n = 474$ （交替 `474` 非幸运数）、 $n = 10^6$
3	30	12~20	$1 \le n \le 5 \times 10^5$
4	25	21~25	$1 \le n \le 10^6$ 随机测试

出处：原题链接

#B4137. [信息与未来 2016] 幸运数字(Lucky Numbers)