시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 3 3 33.333%

문제

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.

입력

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.

출력

For each dataset, output a single line containing an integer ss should be the minimum possible sum w+d+h of three positive integers, w, d, and h, satisfying p=w×d×h.

예제 입력 1

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

예제 출력 1

3
4
6
6
27
1083
6967887
262144
298633
299973
999998765536095