← 返回题目列表

Codeforces · 1345/B

B. 卡片结构

中文机器翻译题面 查看原题

高度 $$$1$$$ 的卡片金字塔是通过将两张卡片相互靠在一起构建的。对于$$$h>1$$$,通过将高度为$$$h-1$$$的卡片金字塔放置在底座上来构建高度为$$$h$$$的卡片金字塔。底座由高度为 $$$1$$$ 的 $$$h$$$ 金字塔和顶部的 $$$h-1$$$ 卡片组成。例如,高度为 $$$1$$$、$$$2$$$ 和 $$$3$$$ 的卡片金字塔如下所示:

你从 $$$n$$$ 卡开始,并尽可能建造最高的金字塔。如果还剩下一些牌,您可以用剩余的牌建造尽可能高的金字塔。你重复这个过程,直到不可能建造另一个金字塔。最后,你会建造多少座金字塔?

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) - 测试用例的数量。接下来的 $$$t$$$ 行包含测试用例的描述。

每个测试用例都包含一个整数 $$$n$$$ ($$$1\le n\le 10^9$$$) — 卡的数量。

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

输出

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

示例

输入 #1

5
3
14
15
24
1

输出 #1

1
2
1
3
0

注意

在第一个测试中,您用 $$$2$$$ 卡构建了一个高度 $$$1$$$ 的金字塔。还剩下 $$$1$$$ 卡,不足以建造金字塔。

在第二个测试中,您建造了两个金字塔,每个金字塔的高度为$$$2$$$,并且没有剩余的卡片。

在第三个测试中,您建造了一座高度 $$$3$$$ 的金字塔,并且没有剩下任何牌。

在第四个测试中,您建造一座高度为 $$$3$$$ 的金字塔,并剩余 $$$9$$$ 卡。然后你建造一个高度为 $$$2$$$ 的金字塔,剩下 $$$2$$$ 卡。然后你建造了一个高度 $$$1$$$ 的最终金字塔,并且没有剩余的卡片。

在第五次测试中,一张卡牌不足以建造任何金字塔。