题目描述
golf
Croce is a battle programmer with top-notch skills, and no one in the programming contest neighborhood knows his name. Algorithms, data mining, hacking, AI, ... I've swept all kinds of competitions. The competition that Kurose set as his next goal is "code golf."
Code golf is a competition for the "shortness of source code" of a program that returns a correct answer to a given question. In code golf, the languages used are often limited because it is difficult to make fair comparisons between different programming languages. At the next competition "ICPC (International Competition of Program Compactness)" that Croce is aiming for, the rule is that only the programming language called "AJAGOL" can be used. In order to shorten the code by as much as one byte, Croce first focused on shortening the "constant declaration".
AJAGOL is a traditional language optimized for the ancient 36-bit architecture. A 36-bit unsigned integer type is prepared to represent an integer, and it can handle integers of $ 0 $ or more and $ 2 ^ {36} -1 $ or less. By the way, the constant of AJAGOL is usually declared as a decimal number using an arbitrary number of numbers [0-9]. In addition, the operators in the table below can be used as operators.
| Priority | Operators | Associativity | Meaning |
|---|---|---|---|
| 1 | (,) | - | Parentheses |
| 2 | ^ | Right join | Exponentiation: a ^ b: = $ a ^ b $ |
| 3 | * | Left join | Multiplication: a * b: = $a \ times b$ |
| 3 | / | Left join | Division: a / b: = $\ lfloor a \ div b \$ |
| 4 | + | Left join | Addition: a + b: = $ a + b $ |
| 4 | - | Left join | Subtract: a-b: = $ a --b $ |
Here, the operation with the smaller priority value is calculated preferentially, and when the values are the same, the calculation is performed in the order according to the associativity. For example, the formula "2 ^ 2 ^ 3 + 8/3 * 2" is 2 ^ 2 ^ 3 + 8/3 * 2 = 2 ^ 8 + 8/3 * 2 = 256 + 8/3 * 2 = 256 It is calculated in the order of + 2 * 2 = 256 + 4 = 260. In addition, calculations where the value in the middle of calculation does not fit in $ [0, 2 ^ {36} -1] $, division by zero, and zero to the power of zero should be avoided because AJAGOL will cause a run-time error. For example, "2 ^ 36-100", "1111/0", "(2-2) ^ 0" will result in a run-time error.
Croce, a top-notch Battle Programmer, found that by using these operators, it was possible to declare constants shorter than usual. For example, 117649 is a well-known $ 7 ^ 6 $, but it can be written as "7 ^ 6" in 3 bytes by using the power operator of AJAGOL. This is 3 bytes shorter than the 6 bytes required by the usual "117649" declaration. Therefore, in code golf by AJAGOL, if you want to use 117649 as a constant, it is basic to declare "7 ^ 6".
Shortening the constant declaration is one of the most basic techniques in code golf, but it can also be said to be a tricky technique. If you spend a lot of time in such a place, you will not be able to spend time shortening the essential code. Therefore, Croce decided to investigate the shortest AJAGOL constant declaration that expresses a non-negative integer when it is input in decimal.
Input
The input consists of multiple datasets. Each dataset is given in one line containing the integer $ N $ ($0 \ leq N \ leq 2 ^ {36} -1$). The end of input is represented by one line containing only $ -1 $.
Output
For each dataset, output the length of the shortest AJAGOL constant declaration representing the given integer $ N $ in one line.
Sample Input
117649
1
125000
1610612736
68719476636
-1
Output for Sample Input
3
1
Four
6
11
Example
Input
117649
1
125000
1610612736
68719476636
-1
Output
3
1
4
6
11
输入格式
见题面
输出格式
见题面