← 返回题目列表

Codeforces · 1419/B

B. 楼梯

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

杰特摧毁了城镇后很累,她想休息一下。她喜欢高处,所以为了休息,她想爬到高处,所以她决定制作楼梯。

楼梯是由方形单元组成的方形图形。每个楼梯由任意数量的楼梯组成。如果楼梯有 $$$n$$$ 个楼梯,则它由 $$$n$$$ 列组成,第一列高 $$$1$$$ 个单元格,第二列高 $$$2$$$ 个单元格,$$$\ldots$$$,如果 $$$n$$$ 个单元格高,则为 $$$n$$$ 第列。所有楼梯的最低单元必须位于同一排。

一个有 $$$n$$$ 楼​​梯的楼梯被称为好楼梯,如果它可能被 $$$n$$$ 由单元格组成的不相交正方形覆盖。所有正方形都应完全由楼梯单元组成。

这就是带有 $$$7$$$ 楼梯的漂亮有盖楼梯的样子:

找出可以建造的不同漂亮楼梯的最大数量,总共使用不超过 $$$x$$$ 单元格。任何电池都不能多次使用。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 1000)$$$ — 测试用例的数量。

每个测试用例的描述都包含一个整数 $$$x$$$ $$$(1 \le x \le 10^{18})$$$ — 用于构建楼梯的单元格数量。

输出

对于每个测试用例,输出一个整数 - 可以构建的不同漂亮楼梯的数量,总共使用不超过 $$$x$$$ 单元格。

示例

输入 #1

4
1
8
6
1000000000000000000

输出 #1

1
2
1
30

注意

在第一个测试用例中,可以只构建一个楼梯,由 $$$1$$$ 楼​​梯组成。很好。这就是为什么答案是$$$1$$$。

在第二个测试用例中,可以构建两个不同的漂亮楼梯:一个由 $$$1$$$ 楼​​梯组成,另一个由 $$$3$$$ 楼​​梯组成。这将花费 $$$7$$$ 细胞。在这种情况下,还剩下一个单元格,但不可能用它来建造任何尚未建造的漂亮楼梯。这就是为什么答案是$$$2$$$。

在第三个测试用例中,可以仅构建两个漂亮楼梯之一:带有 $$$1$$$ 楼​​梯或带有 $$$3$$$ 楼​​梯。在第一种情况下,将剩下 $$$5$$$ 单元格,这些单元格只能用于构建具有 $$$2$$$ 楼​​梯的楼梯。这个楼梯并不好看,杰特只建造了漂亮的楼梯。这就是为什么在本例中答案是 $$$1$$$。如果Jett建造了一个带有$$$3$$$楼梯的楼梯,那么就没有剩余的单元格了,所以答案又是$$$1$$$。