Contest Duration: - (local time) (100 minutes) Back to Home
E - Digit Sum Divisible /

Time Limit: 10 sec / Memory Limit: 1024 MB

### 制約

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

### 入力

N


### 出力

N 以下の良い整数の個数を出力せよ。

### 入力例 1

20


### 出力例 1

13


20 以下の良い整数は 1,2,3,4,5,6,7,8,9,10,12,18,2013 個です。

### 入力例 2

2024


### 出力例 2

409


### 入力例 3

9876543210


### 出力例 3

547452239


Score: 525 points

### Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits in the decimal notation of n. For example, the digit sum of 2024 is 2+0+2+4=8.
A positive integer n is called a good integer when n is divisible by its digit sum. For example, 2024 is a good integer because it is divisible by its digit sum of 8.
You are given a positive integer N. How many good integers are less than or equal to N?

### Constraints

• 1 \leq N \leq 10^{14}
• N is an integer.

### Input

The input is given from Standard Input in the following format:

N


### Output

Print the number of good integers less than or equal to N.

### Sample Input 1

20


### Sample Output 1

13


There are 13 good integers less than or equal to 20: 1,2,3,4,5,6,7,8,9,10,12,18,20.

### Sample Input 2

2024


### Sample Output 2

409


### Sample Input 3

9876543210


### Sample Output 3

547452239