Cube Factory Ltd is an enterprise that sells hcubes (short of "harmonic cubes"), a very fashionable item nowadays providing great profits for his owner, Mr. Tesseract (his friends call him Mr.T).
Mr. T just bought a very large space to fit his increasing stock of hcubes. Hcubes have a plain cube format and are not hard to stock. However, Mr. T has a (rather harmless?) mania: he only admits two valid ways to pile them: (a) in cube format or (b) in squared pyramids (i.e., where each new step holds an increasing square number of elements).
One example of each type (holding, respectively, 43=64 hcubes and 12+22+32+42 = 30 hcubes):
Given N hcubes, find the minimal number of valid piles to stock them according to Mr. T rules.
Example: to stock 38 hcubes we only need two piles: e.g., one cube of height 2 (holding 8 hcubes) and a pyramid of height 4 (holding 30 hcubes).
The input file contains several lines. Each line consists of a single integer representing the number N of hcubes (0 <= N <= 400.000). The file ends in a line with the number –1.
For each N in the input file, a line containing the corresponding result.