题目描述

高度为 $1$ 的纸牌金字塔是通过将两张纸牌相互靠在一起搭建而成的。对于 $h>1$，高度为 $h$ 的纸牌金字塔是通过在一个底座上放置一个高度为 $h-1$ 的纸牌金字塔搭建而成。一个底座由 $h$ 个高度为 $1$ 的金字塔和 $h-1$ 张放在顶部的纸牌组成。例如，高度为 $1$、$2$ 和 $3$ 的纸牌金字塔如下图所示：

你有 $n$ 张纸牌，并且要搭建尽可能高的金字塔。如果还有剩余的纸牌，就用剩下的纸牌再次搭建尽可能高的金字塔。如此反复，直到无法再搭建新的金字塔为止。最后，你一共搭建了多少个金字塔？

输入格式

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

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

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

输出格式

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

说明/提示

在第一个测试用例中，你用 $2$ 张纸牌搭建了一个高度为 $1$ 的金字塔。剩下 $1$ 张纸牌，不足以再搭建一个金字塔。

在第二个测试用例中，你搭建了两个高度为 $2$ 的金字塔，纸牌正好用完。

在第三个测试用例中，你搭建了一个高度为 $3$ 的金字塔，纸牌正好用完。

在第四个测试用例中，你先用 $9$ 张纸牌搭建了一个高度为 $3$ 的金字塔，剩下 $9$ 张纸牌。然后用剩下的纸牌搭建一个高度为 $2$ 的金字塔，剩下 $2$ 张纸牌。最后用剩下的纸牌搭建一个高度为 $1$ 的金字塔，纸牌正好用完。

在第五个测试用例中，只有一张纸牌，无法搭建任何金字塔。

由 ChatGPT 4.1 翻译

样例

5
3
14
15
24
1

1
2
1
3
0