acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem C

荷物

横浜君はいくつかの荷物の配送料金を見積もるところだ. 荷物の配送料金は,それぞれ整数値に切り上げられた, 幅 w, 奥行 d, 高さ h に基づいている. 配送料金はそれらの「和」に比例する.

配送する荷物の一覧はあるのだが,手違いにより そこにあるのは各荷物の幅,奥行,高さの「積」 w×d×h であって, 「和」 w+d+h ではない. この情報だけでは配送料金を正確に計算できない.

そこで横浜君は配送料金の最小値を見積もることにした. そのためには一覧中に記された各荷物の「積」 p に対して, p=w×d×h を満たす 最小の「和」 s=w+d+h を求める必要がある.

あなたには, 与えられた積 p に対して, 和の最小値 s を計算するプログラムを書いて横浜君を助けてほしい.

Input

入力は複数のデータセットからなる. 各データセットは 1 行で,ひとつの整数 p (0 < p < 1015) が記されている.

入力の終わりは,ゼロひとつからなる行で表される.

データセットは300個以内である.

Output

各データセットについて,整数 s ひとつからなる行を出力せよ. sp=w×d×h を満たすみっつの正整数 w, d, h の和 w+d+h の最小値である.

Sample Input

1
2
6
8
729
47045881
12137858827249
562949953421312
986387345919360
999730024299271
999998765536093
0

Output for the Sample Input

3
4
6
6
27
1083
6967887
262144
298633
299973
999998765536095
(End of Problem C) A B C D E F G H