Hyper Hexagonality X17088

An old Measharan proverb says that a good day must include a reference to hexagons. Ronald Zynoulus has received his prize from Gill Bytes, in a huge amount of coins. Thus, he has started to arrange them in hexagonal patterns on his game board. He called a number $N$ hexagonal iff there is a regular hexagon on a hex grid which contains exactly $N$ hexes. Thus, the first four hexagonal numbers are: 1, 7, 19, 37.

                                       * * * *
                          * * *       * * * * *
                 * *     * * * *     * * * * * *
            *   * * *   * * * * *   * * * * * * *
                 * *     * * * *     * * * * * *
                          * * *       * * * * *
                                       * * * *

Ronald wants to use all of his $K$ coins to build such hexagons. Each non-negative integer can be written as a sum of hexagonal numbers, for example, $27 = 19 + 7 + 1$. Of course, he would like to use as few hexagons as possible. He called the smallest number of hexagonal components of $K$ the hyperhexagonality of $K$.

Your task is to calculate the hyperhexagonality of the given number.

Input

Input consists of $T$ cases ($T \leq 100$). Each case is a single number $K$, $1 \leq K \leq 10^{12}$. The input ends with 0.

Output

For each $K$ in the input, output its hyperhexagonality.