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 ≤ 100). Each case is a single number K, 1 ≤ K ≤ 10¹². The input ends with 0.

Output

For each K in the input, output its hyperhexagonality.