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:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll OF_MAX = (1LL<<36)-1;
const ll LEN_MAX = 11;
ll LENGTH[LEN_MAX+1];

inline ll mul(const ll &a, const ll &b){
  if(!a || !b)return 0;
  if( b > OF_MAX/a )return OF_MAX+1;
  return a*b;
}

inline int len(const ll &a){
  return upper_bound(LENGTH,LENGTH+LEN_MAX+1,a) - LENGTH;
}

ll N;
int res;
map<ll,int> pows;
vector<ll> power[LEN_MAX+1];

inline int len_cp(const ll &a){
  return (pows.find(a)!=pows.end())?pows[a]:len(a);
}

//0:+ 1:- 2:* 3:/
inline int check(const ll &n, const ll &x, const int &op){
  switch(op){
  case 0:
    return (n>=x)?len_cp(n-x):LEN_MAX;
  case 1:
    return (x>=n)?len_cp(x-n):LEN_MAX;
  case 2:
    return (x && x*(n/x) == n)?len_cp(n/x):LEN_MAX;
  default:
    return (n && x/n && x/(x/n) == n)?len_cp(x/n):LEN_MAX;
  }
}

inline int check_con(const ll &n, const ll &x, const int &op){
  switch(op){
  case 0:
    return (n>=x)?len(n-x):LEN_MAX;
  case 1:
    return (x>=n)?len(x-n):LEN_MAX;
  case 2:
    return (x && x*(n/x) == n)?len(n/x):LEN_MAX;
  default:
    return (n && x/n && x/(x/n) == n)?len(x/n):LEN_MAX;
  }
}

int main(){
  //init LENGTH to measure the length of numbers
  LENGTH[0] = -1; LENGTH[1] = 10;
  for(int i=2;i<=LEN_MAX;i++)LENGTH[i] = LENGTH[i-1]*10; 

  //calculate short powers
  for(ll a=2;mul(a,a)<=OF_MAX;a++){
    ll tmp = a;
    for(ll p=2;(tmp = mul(a,tmp))<=OF_MAX;p++){
      int tmp_len = len(a) + len(p) + 1; 
      if(len(tmp) <= tmp_len)continue;

      if(pows.find(tmp) == pows.end() || pows[tmp] > tmp_len){
	pows[tmp] = tmp_len;
      }
    }
  }

  //divide efficient powers based on length
  for(map<ll,int>::iterator it=pows.begin();it!=pows.end();it++){
    power[it->second].push_back(it->first);
  }

  //possible formula:
  //1: c
  //3: p
  //5: p op c
  //7: p op c op c, p op p
  //9: p op p op c, p op c op p, p op c op c op c, (p - c) * c

  while( scanf("%lld",&N) && (N>=0) ){
    //c and p
    res = len_cp(N);

    //first term of other cases must be p
    for(int l1=3;l1<res-2;l1++)for(ll fp : power[l1]){
	//p op c and p op p
	for(int op=0;op<4;op++)res = min(res, l1+1+check(N,fp,op));
	
	//p +- p op c
	for(int l2=3;l2<res-3-l1;l2++)for(ll sp :power[l2]){	    
	    // p +- p +- c
	    for(int op=0;op<2;op++){
	      if(fp+sp<=OF_MAX)res = min(res, l1+l2+2+check_con(N,fp+sp,op));
	      if(fp-sp>=0)res = min(res, l1+l2+2+check_con(N,fp-sp,op));
	    }

	    // p +- p */ c
	    for(int op=2;op<4;op++){
	      res = min(res, l1+l2+2+check_con(abs(N-fp),sp,op));
	    }
	  }
	if(l1+2>=res)break;

	// p * p op c
	for(int l2=3;l2<res-3-l1;l2++)for(ll sp :power[l2]){
	    if(len(fp*sp)<l1+l2+1)break;
	    if(mul(fp,sp)>OF_MAX)break;
	    for(int op=0;op<4;op++){
	      res = min(res, l1+l2+2+check_con(N,fp*sp,op));
	    }
	  }

	// p / p op c : not needed
	if(l1+2>=res)break;            

	//p * c op cp
	for(ll a=2;;a++){
	  int l2 = len(a);
	  if(l2>=res-3-l1)break;
	  if(mul(fp,a)>OF_MAX)break;
	  if(len(fp*a)<=l1+l2+1)break;
	  for(int op=0;op<4;op++){
	    res = min(res, l1+l2+2+check(N,fp*a,op));
	  }
	}

	if(l1+2>=res)break;

	//p / c op cp
	for(ll a=2;;a++){
	  int l2 = len(a);
	  if(len(fp/a)<=l1+l2+1)break;
	  if(l2>=res-3-l1)break;
	  for(int op=0;op<4;op++){
	    res = min(res,l1+l2+2+check(N,fp/a,op));
	  }
	}

	if(l1+2>=res)break;

	//p +- c op cp is not needed, except p-c+p (the order must be fixed to avoid overflow)
	//in fact, there is no case such that p-c+p is valid but p+p-c is overflow "under constraint [0,2^36-1]"


	if(l1>4)continue;
	if(res<=9)continue;

	//p */ c */ c op c
	int la = 1;
	for(ll a=2;a<100;a++){
	  if(a==10)la++;
	  int lb = 1;
	  if(mul(fp,a)<=OF_MAX && len(fp*a)>l1+la+1){
	    //p * c * c: not needed
	    //p * c / c
	    for(ll b=2;b<100;b++){
	      if(b==10)lb++;
	      if(7<=l1+la+lb)break;
	      for(int op=0;op<4;op++){
		res = min(res, l1+la+lb+3+check_con(N,fp*a/b,op));
	      }
	    }
	  }

	  //p / c * c
	  if(fp>a && len(fp/a)>l1+la+1){
	    lb = 1;
	    for(ll b=2;b<100;b++){
	      if(b==10)lb++;
	      if(7<=l1+la+lb)break;
	      if(mul(fp/a,b)>OF_MAX)break;
	      for(int op=0;op<4;op++){
		res = min(res, l1+la+lb+3+check_con(N,fp/a*b,op));
	      }
	    }

	    //p / c / c
	    lb = 1;
	    for(ll b=2;b<100;b++){
	      if(b==10)lb++;
	      if(7<=l1+la+lb)break;
	      for(int op=0;op<4;op++){
		res = min(res, l1+la+lb+3+check_con(N,fp/a/b,op));
	      }
	    }
	  }

	}

	if(l1<4)continue;
	if(res<=10)continue;
	//(p - c) * c
	//Note that |p| = 4 and |c| = 1 must hold, thus |formula|=10
	for(ll a=1;a<10;a++)for(ll b=1;b<10;b++){
	    if( (fp-a)*b == N )res = min(res,10);
	  }
      }
    printf("%d\n",res);
  }
}