Cubes^squared

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, 4³=64 hcubes and 1²+2²+3²+4² = 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