← 返回题目列表

Codeforces · 1809/B

B. 平面上的点

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

你有一个二维平面,你需要在上面放置 $$$n$$$ 芯片。

您只能将芯片放置在具有整数坐标的点上。在 $$$(x, y)$$$ 点放置筹码的成本等于 $$$|x| + |y|$$$ (其中 $$$|a|$$$ 是 $$$a$$$ 的绝对值)。

放置 $$$n$$$ 筹码的成本等于每个筹码成本中的最大值。

您需要将 $$$n$$$ 筹码放置在平面上,使得每对筹码之间的欧氏距离严格大于 $$$1$$$,并且成本尽可能最小。

输入

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

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — 您需要放置的芯片数量。

输出

对于每个测试用例,打印一个整数 - 如果每对芯片之间的距离必须严格大于 $$$1$$$,则放置 $$$n$$$ 芯片的最低成本。

示例

输入 #1

4
1
3
5
975461057789971042

输出 #1

0
1
2
987654321

注意

在第一个测试用例中,您可以将唯一的芯片放置在点 $$$(0, 0)$$$ 处,总成本等于 $$$0 + 0 = 0$$$。

在第二个测试用例中,您可以将筹码放置在点 $$$(-1, 0)$$$、$$$(0, 1)$$$ 和 $$$(1, 0)$$$ 上,成本为 $$$|-1| + |0| = 1$$$, $$$|0| + |1| = 1$$$ 和 $$$|0| + |1| = 1$$$。每对芯片之间的距离大于 $$$1$$$(例如,$$$(-1, 0)$$$ 和 $$$(0, 1)$$$ 之间的距离等于 $$$\sqrt{2}$$$)。总成本等于 $$$\max(1, 1, 1) = 1$$$。

在第三个测试用例中,您可以将筹码放置在点 $$$(-1, -1)$$$、$$$(-1, 1)$$$、$$$(1, 1)$$$、$$$(0, 0)$$$ 和 $$$(0, 2)$$$ 处。总成本等于 $$$\max(2, 2, 2, 0, 2) = 2$$$。