D. Hard Tasks
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

After math class, Teacher Awson gave Sinoey $$$n$$$ tasks as his homework, the $$$i$$$-th of which is to calculate the sum of $$$3$$$ consecutive integers starting from $$$i-1$$$, i.e. $$$(i-1)+i+(i+1)$$$. Note that he does not need to calculate $$$i-1$$$ or $$$i+1$$$.

It is a big problem for Sinoey because he does not want to carry even once! For two numbers represented as $$$\overline{x_n\dots x_2x_1}$$$ and $$$\overline{y_n\dots y_2y_1}$$$, carrying means there exists an integer $$$i\ (1\le i\le n)$$$ such that $$$x_i+y_i\ge 10$$$. Take the $$$4$$$th task, $$$3+4+5$$$ as an example. Since $$$3+4+5 \gt 10$$$, Sinoey will have to minus the first digit by $$$10$$$ and add $$$1$$$ to the next digit in order to get the correct answer.

Carrying is awful, and Sinoey decides to do only the tasks that do not require carrying. Now you need to tell him the number of tasks he will do.

Input

The only line of the input contains an integer $$$n\ (1\le n\le 10^{18})$$$, the total number of tasks.

Output

Print an integer representing the number of tasks Sinoey decides to do.

Scoring

The problem contains several subtasks. You can get the corresponding score for each passed test case.

  • Subtask 1 ($$$30$$$ points): $$$n\le 10^6$$$.
  • Subtask 2 ($$$30$$$ points): $$$n\le 10^{10}$$$.
  • Subtask 3 ($$$40$$$ points): no additional constraints.
Examples
Input
12
Output
5
Input
141214
Output
1536
Note

In the first example, task $$$1,2,3,11$$$ and $$$12$$$ are easy.