当 Bajtbara 还是个小女孩的时候，她喜欢把立方体积木摆成正方形。她拿到一定数量的积木，试图把它们分成尽可能少的正方形。她总是能做到，使得正方形的数量不超过四个。

如今 Bajtbara 已经长大成人，赚着数以万亿计的 bajtalar，而不再玩积木了。最近她读到：任意自然数都可以表示为至多四个平方数之和。此外，任意数都可以表示为至多三个三角形数（即形如 $\frac{n(n+1)}{2}$ 的数）之和。这让她联想起童年的游戏，于是开始用硬币来玩。不过这一次，她不是把硬币摆成正方形或三角形，而是摆成六边形。

                                       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

对于给定数量的硬币，Bajtbara 想知道最少可以把它们分成多少个六边形。例如，27 枚硬币可以分成 3 个六边形（27 = 1 + 7 + 19）。

输入格式

输入由 $T$ 个测试组成（$T \le 1000$）。对于 $1 \le i \le T$，输入的第 $i$ 行包含一个整数 $K_i$（$1 \le K_i \le 10^{12}$），表示 Bajtbara 拥有的硬币数量。

在输入的第 $T+1$ 行有一个数 0，表示输入结束。

在占 20% 分值的测试中，满足条件 $K_i \le 1\ 000\ 000$。

输出格式

对于每个给定的硬币数量，输出可以将其分成的最少六边形数量。

样例数据

对于输入数据：

1
6
7
19
27
0

正确的输出为：

1
6
1
1
3