CF1345B.Card Constructions

A card pyramid of height $1$ is constructed by resting two cards against each other. For $h \gt 1$, a card pyramid of height $h$ is constructed by placing a card pyramid of height $h-1$ onto a base. A base consists of $h$ pyramids of height $1$, and $h-1$ cards on top. For example, card pyramids of heights $1$, $2$, and $3$ look as follows:

You start with $n$ cards and build the tallest pyramid that you can. If there are some cards remaining, you build the tallest pyramid possible with the remaining cards. You repeat this process until it is impossible to build another pyramid. In the end, how many pyramids will you have constructed?

高度为 $1$ 的纸牌金字塔由两张纸牌相互倚靠构成。对于 $h > 1$，高度为 $h$ 的纸牌金字塔通过将一个高度为 $h-1$ 的纸牌金字塔置于一个底座之上而构成。该底座由 $h$ 个高度为 $1$ 的纸牌金字塔以及其上方的 $h-1$ 张纸牌组成。例如，高度分别为 $1$、$2$ 和 $3$ 的纸牌金字塔如下图所示：

你初始拥有 $n$ 张纸牌，并尽可能建造最高的纸牌金字塔。若建造后仍有剩余纸牌，则用剩余纸牌继续建造可能的最高金字塔。重复此过程，直至无法再建造任何金字塔为止。最终，你一共建造了多少座金字塔？

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

Each test case contains a single integer $n$ ($1\le n\le 10^9$) — the number of cards.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^9$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\le t\le 1000$），表示测试用例的数量。接下来的 $t$ 行分别描述各个测试用例。

每个测试用例包含一个整数 $n$（$1\le n\le 10^9$），表示卡片的数量。

保证所有测试用例中 $n$ 的总和不超过 $10^9$。

For each test case output a single integer — the number of pyramids you will have constructed in the end.

对于每个测试用例，输出一个整数——最终你所构建的金字塔数量。

In the first test, you construct a pyramid of height $1$ with $2$ cards. There is $1$ card remaining, which is not enough to build a pyramid.

In the second test, you build two pyramids, each of height $2$, with no cards remaining.

In the third test, you build one pyramid of height $3$, with no cards remaining.

In the fourth test, you build one pyramid of height $3$ with $9$ cards remaining. Then you build a pyramid of height $2$ with $2$ cards remaining. Then you build a final pyramid of height $1$ with no cards remaining.

In the fifth test, one card is not enough to build any pyramids.

在第一个测试中，你用 2 张卡片构建了一个高度为 $1$ 的金字塔，剩余 1 张卡片，不足以再构建任何金字塔。

在第二个测试中，你构建了两个高度均为 $2$ 的金字塔，没有剩余卡片。

在第三个测试中，你构建了一个高度为 $3$ 的金字塔，没有剩余卡片。

在第四个测试中，你首先用部分卡片构建了一个高度为 $3$ 的金字塔，剩余 9 张卡片；接着用其中一部分构建了一个高度为 $2$ 的金字塔，剩余 2 张卡片；最后用剩余卡片构建了一个高度为 $1$ 的金字塔，没有剩余卡片。

在第五个测试中，仅有 1 张卡片，不足以构建任何金字塔。