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). Input 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’. Output For each N in the input file, a line containing the corresponding result. Sample Input 38 60 12 39101 -1 Sample Output 2 2 4 4