M. Baby Ehab's Whining Chance
time limit per test
1 second
memory limit per test
256 megabytes
input
lis.in
output
standard output

Baby Ehab had just been stung by increasing subsequences in IOI, so he decided to make himself feel better about his skills. He chose an integer $$$n$$$, wrote down all integers from $$$1$$$ to $$$n$$$, and calculated the longest increasing subsequence like a true genius! Enter Baby Badawy again as envious as ever.

Baby Badawy decided to play a trick on Baby Ehab. He replaced every integer in the sequence with the sum of its digits. Of course, Baby Ehab started crying. It was IOI all over again!

So, his "babysitter" Laggy hired you to find the longest increasing subsequence of this sequence so that Baby Ehab would stop crying.

Hurry up! You only have 300 minutes before Baby Ehab dies of dehydration.

Input

The only line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10 ^ {100000})$$$.

Output

Print the longest increasing subsequence required in the statement.

Examples
Input
10
Output
9
Input
99
Output
18
Input
777
Output
24