D. House Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You originally joined Columbia Space Initiative to build and program rockets, but ever since Columbia Housing colonized a distant planet and finished a set of new constructions, your duties have been reassigned. You are about to board the spaceship to the new planet, Carlton Legs, when you remember you'll need to buy metal house numbers to affix to the front of your new house (so it can be identified for maintenance). Unfortunately, the 250 light-year journey back is reserved for Columbia Housing staff, so you'll need to buy your house numbers before you leave.

You know that there are only $$$n$$$ houses on the planet, numbered from $$$1$$$ to $$$n$$$, but you aren't sure which one you've been assigned. University Hardware sells individual metal digits $$$0$$$–$$$9$$$ for $$$1$$$ dollar apiece, with an infinite supply of each digit, and you can buy as many digits as necessary to label your house. What is the minimal amount you must spend to ensure that, regardless of which house number you are assigned, you'll be able to label your house using the digits you bought?

Input

The first and only line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$), the maximal house number you could be assigned.

Output

Output one integer — the minimal number of digits $$$0$$$–$$$9$$$ you'll need to buy to ensure that any house number from $$$1$$$ to $$$n$$$ can be written using them.

Examples
Input
7
Output
7
Input
17
Output
11
Input
6666667
Output
66
Note

In example 1, you can buy the digits $$$1$$$ through $$$7$$$, which can be used to make each house number from $$$1$$$ through $$$7$$$.

In example 2, you can buy one $$$0$$$, two $$$1$$$s, and one of each digit $$$2$$$–$$$8$$$. It can be shown that the numbers $$$1$$$–$$$17$$$ can each be created using only these digits. For example, $$$11$$$ uses both of the $$$1$$$s, and $$$17$$$ uses one $$$1$$$ and one $$$7$$$.