题目描述

我们将正整数 $n$ 的各位数字之和定义为将 $n$ 用十进制表示时各位数字的和。例如，$2024$ 的各位数字之和为 $2+0+2+4=8$。
当正整数 $n$ 能被其各位数字之和整除时，我们称 $n$ 为好整数。例如，$2024$ 能被其各位数字之和 $8$ 整除，因此是好整数。
给定一个正整数 $N$，请你计算不超过 $N$ 的好整数有多少个。

输入格式

输入包含一行，格式如下：

$N$

输出格式

输出不超过 $N$ 的好整数的个数。

样例 1

输入

20

输出

13

样例 2

输入

2024

输出

409

样例 3

输入

9876543210

输出

547452239

说明/提示

限制

• $1 \leq N \leq 10^{14}$
• $N$ 是整数

样例解释 1

不超过 $20$ 的好整数有 $1,2,3,4,5,6,7,8,9,10,12,18,20$ 共 $13$ 个。

由 ChatGPT 4.1 翻译