// 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;
	}
}

Measured memory_bytes: 67456