ゴルフ

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

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

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

ここで，優先順位の値が小さい演算ほど優先的に計算され，同じ値のときには結合性に従った順序で計算される． 例えば "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