A. 1s For All
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The em complexity of an integer is the minimum number of $$$1$$$'s needed to represent it using only addition, multiplication and parentheses. For example, the complexity of $$$2$$$ is $$$2$$$ (writing $$$2$$$ as $$$1+1$$$) and the complexity of $$$12$$$ is $$$7$$$ (writing $$$12$$$ as $$$(1+1+1)\times (1+1+1+1)$$$). We'll modify this definition slightly to allow the concatenation operation as well. This operation (which we'll represent using $$$\oplus$$$) takes two integers and "glues" them together, so $$$12\ \oplus 34$$$ becomes the four digit number $$$1234$$$. Using this operation, the complexity of $$$12$$$ is now $$$3$$$ (writing it either as $$$(1 \oplus 1) + 1$$$ or $$$1 \oplus (1+1)$$$). Note that the concatenation operation ignores any initial zeroes in the second operand: $$$1 \oplus 01$$$ does not result in $$$101$$$ but results in $$$11$$$.

Input

Each test case consists of a single line containing an integer $$$n$$$, where $$$0 \lt n \leq 100\, 000$$$.

Output

Output the complexity of the number, using the revised definition above.

Examples
Input
2
Output
2
Input
12
Output
3