acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem C

Luggage

Mr. Yokohama is estimating the delivery fare for a number of luggage pieces. The fare for a piece is determined by its width w, depth d and height h, each rounded up to an integer. The fare is proportional to the sum of them.

The list of the luggage pieces is at hand, but the list has the product w×d×h for each piece, instead of the sum w+d+h by mistake. This information is not enough to calculate the exact delivery fare.

Mr. Yokohama therefore decided to estimate the minimum possible delivery fare. To this end, given the listed product p for each of the luggage pieces, the minimum possible sum s=w+d+h satisfying p=w×d×h should be found.

You are requested to help Mr. Yokohama by writing a program that, when given the product p, computes the minimum sum s.

Input

The input consists of multiple datasets. Each of the datasets has one line containing an integer p (0 < p < 1015).

The end of the input is indicated by a line containing a zero.

The number of datasets does not exceed 300.

Output

For each dataset, output a single line containing an integer s. s should be the minimum possible sum w+d+h of three positive integers, w, d, and h, satisfying p=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