Kiedy Bajtbara was a little girl, she liked arranging cubic blocks into squares. She took some number of blocks and tried to split them into the smallest possible number of squares. She always managed to do it so that there were at most four squares.

Today Bajtbara is an adult and earns billions of bajtalars instead of playing with blocks. Recently she read that every natural number is a sum of at most four squares. Moreover, every number is a sum of at most three triangular numbers (that is, numbers of the form $\frac{n(n+1)}{2}$). This reminded her of her childhood game, and she started playing with coins. However, instead of arranging coins into squares or triangles, she started arranging them into hexagons.

                                       O O O O
                          O O O       O O O O O
                 O O     O O O O     O O O O O O
            O   O O O   O O O O O   O O O O O O O
                 O O     O O O O     O O O O O O
                          O O O       O O O O O
                                       O O O O

For a given number of coins, Bajtbara wants to know into the smallest number of hexagons it can be split. For example, 27 coins can be split into 3 hexagons (27 = 1 + 7 + 19).

Input Format

The input consists of $T$ test cases ($T \le 1000$). For $1 \le i \le T$, the $i$-th line of the input contains an integer $K_i$ ($1 \le K_i \le 10^{12}$) — the number of coins Bajtbara has.

The $(T+1)$-th line of the input contains the number 0, which marks the end of the input.

In tests worth 20% of the points, the condition $K_i \le 1\ 000\ 000$ holds.

Output Format

For each of the $T$ numbers of coins, output the smallest number of hexagons into which it can be split.

Example

For the input data:

1
6
7
19
27
0

the correct output is:

1
6
1
1
3