← 返回题目列表

Codeforces · 1487/D

D. 毕达哥拉斯三元组

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

毕达哥拉斯三元组是整数 $$$(a, b, c)$$$ 的三元组,这样可以形成一个直角三角形,其第一内角、第二内角和斜边的长度分别等于 $$$a$$$、$$$b$$$ 和 $$$c$$$。毕达哥拉斯三元组的一个例子是 $$$(3, 4, 5)$$$。

Vasya 研究直角三角形的性质,他使用一个公式来确定某些整数三元组是否是勾股数。不幸的是,他忘记了确切的公式;他只记得这个公式是一些平方方程。于是,他想出了下面的公式:$$$c = a^2 - b$$$。

显然,这不是检查三重数是否为勾股数的正确公式。但是,令 Vasya 惊讶的是,它实际上适用于三元组 $$$(3, 4, 5)$$$:$$$5 = 3^2 - 4$$$,因此,根据 Vasya 的公式,它是一个毕达哥拉斯三元组。

当 Vasya 找到正确的公式(并明白他的公式是错误的)时,他想知道:有多少个整数 $$$(a, b, c)$$$ 与 $$$1 \le a \le b \le c \le n$$$ 的三元组,使得根据他的公式和真正的定义它们都是毕达哥拉斯的?他让你数一下这些三元组。

输入

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

每个测试用例由一行组成,其中包含一个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$)。

输出

对于每个测试用例,打印一个整数 - 整数三元组的数量 $$$(a, b, c)$$$ 与 $$$1 \le a \le b \le c \le n$$$ 使得它们根据实际定义和 Vasya 提出的公式都是毕达哥拉斯的。

示例

输入 #1

3
3
6
9

输出 #1

0
1
1

注意

满足 $$$c = a^2 - b$$$ 且 $$$1 \le a \le b \le c \le 9$$$ 的唯一毕达哥拉斯三元组是 $$$(3, 4, 5)$$$;这就是为什么 $$$n = 3$$$ 的答案是 $$$0$$$,$$$n = 6$$$(以及 $$$n = 9$$$)的答案是 $$$1$$$。