2710. Just Too Lucky

单点时限: 5.0 sec

内存限制: 256 MB

Since mass transit was invented, people who buy tickets look for lucky ticket numbers. There are many notions of lucky tickets, for example sometimes tickets are considered lucky if the sum of first half of the digits is equal to the sum of the second half, sometimes the product is used instead of the sum, sometimes permutation of digits is allowed, etc.

In St Andrewburg integer numbers from $1$ to $n$ are used as ticket numbers. Bill considers a ticket lucky if its number is divisible by the sum of its digits. Help Bill to find the number of lucky tickets.

输入格式

The first line of the input file contains $n$ ($1 \le n \le 10^{12}$).

输出格式

Output one number ― the number of lucky tickets.

样例

Input
100
Output
33

2 人解决,12 人已尝试。

11 份提交通过,共有 28 份提交。

9.4 EMB 奖励。

创建: 15 年,11 月前.

修改: 6 年,8 月前.

最后提交: 1 年,2 月前.

来源: NEERC 2008

题目标签
dfs