Golf | cho.sh

문제

クロセは超一流の腕を持ったバトルプログラマーであり，プログラミングコンテスト界隈でその名を知らぬ者はいない．アルゴリズム，データマイニング，ハッキング，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定数宣言として最も短いものを調べることにした．

입력

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

출력

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