24555번 - 1’s For All 다국어

문제

The 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 ©) takes two integers and "glues" them together, so 12ドル\ $©$\ 34$ becomes the four digit number 1234ドル$. Using this operation, the complexity of 12ドル$ is now 3ドル$ (writing it either as $(1 \ $©$\ 1) + 1$ or 1ドル\ $©$\ (1+1)$). Note that the concatenation operation ignores any initial zeroes in the second operand: 1ドル\ $©$\ 01$ does not result in 101ドル$ but results in 11ドル$.

We'll give you 1ドル$ guess what the object of this problem is.

입력

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

출력

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

제한

힌트