Kiedy Bajtbara była małą dziewczynką, lubiła układać sześcienne klocki w kwadraty. Brała pewną liczbę klocków i starała się podzielić je na jak najmniejszą liczbę kwadratów. Zawsze udawało jej się zrobić to tak, żeby tych kwadratów było co najwyżej cztery.

Dzisiaj Bajtbara jest już dorosła i zarabia biliony bajtalarów, zamiast bawić się klockami. Ostatnio przeczytała, że każda liczba naturalna jest sumą co najwyżej czterech kwadratów. Ponadto, każda liczba jest sumą co najwyżej trzech liczb trójkątnych (czyli liczb postaci $\frac{n(n+1)}{2}$). Skojarzyło jej się to z jej zabawą z dzieciństwa i zaczęła się bawić monetami. Jednak zamiast układać monety w kwadraty albo trójkąty, zaczęła układać je w sześciokąty.

                                       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

Dla danej liczby monet Bajtbara chce wiedzieć, na jaką najmniejszą liczbę sześciokątów można ją podzielić. Na przykład 27 monet można podzielić na 3 sześciokąty (27 = 1 + 7 + 19).

Wejście

Wejście składa się z $T$ testów ($T \le 1000$). Dla $1 \le i \le T$, w i-tym wierszu wejścia znajduje się liczba $K_i$ ($1 \le K_i \le 10^{12}$) - liczba monet, którą dysponuje Bajtbara.

W wierszu $T + 1$ wejścia znajduje się liczba 0, oznaczająca koniec wejścia.

W testach wartych 20% punktów zachodzi warunek $K_i \le 1\ 000\ 000$.

Wyjście

Dla każdej z $T$ liczb monet podaj najmniejszą liczbę sześciokątów, na które można ją podzielić.

Przykład

Dla danych wejściowych:

1
6
7
19
27
0

poprawną odpowiedzią jest:

1
6
1
1
3