Space Coconut Crab

Ken Marineblue is a space hunter who travels the entire galaxy in search of the space coconut crab. The space coconut crab is said to be the largest crustacean in the universe: once grown, its body length exceeds 400 meters, and with its legs spread it reaches over 1,000 meters. Many people have already sighted the space coconut crab, but no one has succeeded in capturing one.

Through long-term research, Ken uncovered an important fact about the space coconut crab's ecology. Astonishingly, the space coconut crab does the equivalent of the latest warp technology, called phase-transition navigation, and lives by traveling back and forth between normal space and hyperspace. He also determined that it takes a long time for the space coconut crab to warp out from hyperspace into normal space, and that for a while after warping out it cannot move into hyperspace.

So Ken finally set out to capture the space coconut crab. His strategy is as follows. First, he observes the energy with which the space coconut crab plunges from normal space into hyperspace. When this energy is e, the coordinates (x, y, z) at which the space coconut crab warps out from hyperspace are known to satisfy the following conditions.

• x, y, and z are all nonnegative integers.
• x + y2 + z3 = e.
• Under the conditions above, the value of x + y + z is minimized.

These conditions alone do not always determine the coordinates uniquely, but when the minimum value of x + y + z is m, the coordinates at which it warps out are certainly on the plane x + y + z = m. So Ken stretches a sufficiently large barrier over this plane. The space coconut crab then warps out onto the barrier. Affected by the barrier, the space coconut crab cannot move. There Ken plans to capture it with the Weapon Breaker, the state-of-the-art spacecraft he pilots.

The barrier can be stretched only once, so failure is not an option. Ken therefore decided to enlist the help of a computer for the mission. Your job is to write a program that, given the energy with which the space coconut crab plunges into hyperspace, finds the plane x + y + z = m on which the barrier must be stretched. Your program will be accepted when it prints the correct result for every prepared test case.

The input consists of multiple datasets. Each dataset has a single line containing one positive integer e (e ≦ 1,000,000), which represents the energy with which the space coconut crab plunged into hyperspace. The input ends when e = 0, and this value is not included in the datasets.

For each dataset, print the value of m on one line. The output must not contain any other characters.