Problem: 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 \ rfloor $
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

Solution (in CPP):

Solution:
// 2014Domestic G:Golf (pes)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

const long long MAX_VALUE = 1LL<<36;
const long long MAX_DIGIT = 11;

vector< pair<int, long long> > power;
map<long long, int> term;
vector<long long> termV[9];

int getLength(long long t){
	int res = 1;
	for(long long i=t;i>=10;i/=10){
		res++;
	}
	return res;
}

int getTermLen(long long t){
	if(term.count(t)) return term[t];
	return getLength(t);
}

bool checkUpdate(long long value, int length){
	if(length < getLength(value)){
		if(term.count(value)){
			int curBest = term[value];
			if(length < curBest){
				term[value] = length;
				return true;
			}
		} else {
			term[value] = length;
			return true;
		}
	}
	return false;
}

void makePower(){
	for(long long i=2;i*i<MAX_VALUE;i++){
		long long value = i*i;
		int p = 2;
		int baseLen = getLength(i);
		while(value < MAX_VALUE){
			int length = baseLen + getLength(p) + 1;
			checkUpdate(value, length);
			value *= i;
			p++;
		}
	}
	for(map<long long, int>::iterator it=term.begin(), end=term.end();it!=end;++it){
		power.push_back(make_pair(it->second, it->first));
	}
	sort(power.begin(), power.end());
}

void termSearch(long long curValue, int curLength, bool mul){
	if(curLength >= getLength(curValue)-1) return ;
	for(long long i=2;;++i){
		long long nextValue = mul ? curValue*i : curValue/i;
		long long nextLen = curLength + getLength(i) + 1;
		if(nextValue >= MAX_VALUE) break;
		if(nextLen > MAX_DIGIT-3) break;
		if(nextLen >= getLength(nextValue)){
			if(!mul) break;
			continue;
		}
		if(checkUpdate(nextValue, nextLen) && nextLen <= MAX_DIGIT-5){
			termSearch(nextValue, nextLen, !mul);
		}
	}
}

void makeTerm(){
	for(int i=0;i<power.size();i++){
		termSearch(power[i].second, power[i].first, true);
		termSearch(power[i].second, power[i].first, false);
	}
	for(map<long long, int>::iterator it=term.begin(),end=term.end();it!=end;++it){
		termV[it->second].push_back(it->first);
	}
}

void precalc(){
	power.clear();
	term.clear();
	makePower();
	makeTerm();
}

int getDivNum(long long a, long long b){
	int R = a/(b+1)+1;
	if(a/R == b) return R;
	return -1;
}

int solve(const long long s){
	int res = getLength(s);
	if(term.count(s)) res = term[s];
	for(int i=1;i<=8;i++){
		int baseLen = i;
		if(baseLen+2 >= res) break;
		for(int j=0;j<termV[i].size();j++){
			long long baseValue = termV[i][j];
			// baseValue +- v = s
			long long v = abs(s - baseValue);
			if(v < MAX_VALUE){
				res = min(res, baseLen + getTermLen(v) + 1);
			}
			// baseValue * v = s
			if(s%baseValue == 0){
				v = s/baseValue;
				res = min(res, baseLen + getTermLen(v) + 1);
			}
			// baseValue / v = s
			v = getDivNum(baseValue, s);
			if(v != -1){
				res = min(res, baseLen + getLength(v) + 1);
			}
		}
	}
	for(int i=0;i<power.size();i++){
		// (power[i].second-v)*t
		for(int v=1;;v++){
			int lenV = getLength(v);
			if(power[i].first+lenV+3 > res-2) break;
			long long baseValue = power[i].second - v;
			if(baseValue < 0) break;
			if(s%baseValue == 0){
				long long t = s/baseValue;
				res = min(res, power[i].first+lenV+4+getLength(t));
			}
		}
		for(int j=0;j<i;++j){
			if(power[i].first + power[j].first > res-2) break;
			// pow2つ
			long long valA = power[i].second;
			long long valB = power[j].second;
			if(power[i].first + power[j].first + 3 < res){
				// valA + valB +- v
				long long v = abs(s - (valA+valB));
				res = min(res, power[i].first + power[j].first + getLength(v) + 2);
				// valA - valB +- v
				v = abs(s - abs(valA-valB));
				res = min(res, power[i].first + power[j].first + getLength(v) + 2);
			}
			if((double)valA*valB < 1e15 && valA*valB < MAX_VALUE){
				// valA * valB
				if(valA*valB == s){
					res = min(res, power[i].first + power[j].first + 1);
				}
				if(power[i].first + power[j].first + 3 < res){
					// valA * valB +- v
					long long v = abs(s - valA*valB);
					res = min(res, power[i].first + power[j].first + getLength(v) + 2);
					// valA * valB / v
					v = getDivNum(valA*valB, s);
					if(v != -1){
						res = min(res, power[i].first + power[j].first + getLength(v) + 2);
					}
				}
			}
		}
	}
	return res;
}

int main(){
	precalc();
	long long s;
	while(cin >> s && ~s){
		cout << solve(s) << endl;
	}
}