ゴルフ

クロセは超一流の腕を持ったバトルプログラマーであり,プログラミングコンテスト界隈でその名を知らぬ者はいない. アルゴリズム,データマイニング,ハッキング,AI,……ありとあらゆる大会を総なめにしてきた. そんなクロセが次の目標に据えた競技は,「コードゴルフ」である.

コードゴルフとは,与えられた問題に対し正答を返すプログラムの「ソースコードの短さ」を競う競技である. コードゴルフにおいては,異なるプログラミング言語間で公平な比較が難しいため,使用言語が限定されることが多い. クロセが次に狙っている大会「ICPC (International Competition of Program Compactness)」では, 「AJAGOL」と呼ばれるプログラミング言語のみが使用できるルールとなっている. コードを1バイトでも短くするため,クロセが初めに注目したのは,「定数宣言」の短縮だった.

AJAGOLはいにしえの36bitアーキテクチャに最適化して設計された伝統ある言語である. 整数を表現するために36bit符号無し整数型が用意されており,$0$ 以上 $2^{36}-1$ 以下の整数を扱うことができる. さて,AJAGOLの定数は通常,数字[0-9]を任意の個数用いた十進数で宣言される. また,演算子として以下の表の演算子を用いることができる.

優先順位演算子結合性意味
1( , )-括弧
2^右結合冪乗: a^b := $a^b$
3*左結合乗算: a*b := $a \times b$
3/左結合除算: a/b := $ \lfloor a \div b \rfloor$
4+左結合加算: a+b := $a + b$
4-左結合減算: a-b := $a - b$

ここで,優先順位の値が小さい演算ほど優先的に計算され,同じ値のときには結合性に従った順序で計算される. 例えば "2^2^3+8/3*2" という計算式は,2^2^3+8/3*2 = 2^8+8/3*2 = 256+8/3*2 = 256+2*2 = 256+4 = 260 という順序で計算される. また,演算途中の値が $[0, 2^{36}-1]$ に収まらない計算やゼロ除算,ゼロのゼロ乗は,AJAGOLでは実行時エラーとなるため避ける必要がある. 例えば "2^36-100","1111/0","(2-2)^0" などは実行時エラーとなる.

超一流のバトルプログラマーであるクロセは,これらの演算子を用いることにより,通常よりも短い定数宣言が可能であることを見抜いた. 例えば,117649は言わずと知れた $7^6$ であるが,AJAGOLの冪乗演算子を用いることで "7^6" と3バイトで書くことができる. これは通常の "117649" という宣言で必要となる6バイトよりも3バイト短い. よって,AJAGOLによるコードゴルフでは,117649を定数として用いたい場合には "7^6" と宣言するのが基本となる.

定数宣言の短縮はコードゴルフにおいて最も基本的なテクニックの1つであるが,あくまで小手先のテクニックとも言える. このようなところに多大な時間を掛けていては,本質的なコードの短縮に時間を割けなくなってしまう. そこでクロセは,非負整数を十進数で入力したとき,それを表現するAJAGOL定数宣言として最も短いものを調べることにした.

Input

入力は複数のデータセットからなる. 各データセットは整数 $N$ ($0 \leq N \leq 2^{36}-1$) を含む1行で与えられる. 入力の終了は $-1$ のみを含む1行で表される.

Output

各データセットに対し,与えられた整数 $N$ を表現する最も短いAJAGOL定数宣言の長さを1行で出力せよ.

Sample Input

117649
1
125000
1610612736
68719476636
-1

Output for Sample Input

3
1
4
6
11