题目描述

自从公共交通出现以来，购买车票的人们就一直热衷于寻找“幸运车票”。幸运车票有许多种定义，例如：

• 前一半数字之和等于后一半数字之和；
• 将“和”改为“积”；
• 允许重新排列数字；
• 等等。

在圣安德鲁堡，编号为 $1$ 到 $n$ 的整数被用作车票号码。

Bill 认为，一张车票是幸运的，当且仅当它的号码能够被其各位数字之和整除。

请计算编号在 $1$ 到 $n$ 之间的幸运车票数量。

输入格式

输入一行，包含一个整数 $n$。

输出格式

输出一个整数，表示幸运车票的数量。

样例

输入

100

输出

33

数据范围

• $1\le n\le 10^{12}$。

时间与空间限制

• 时间限制：$3$ 秒；
• 空间限制：$256$ MB。

难度评定

预计 Codeforces 评分：2300。