#P0048. 棋盘落子②

棋盘落子②

题目描述

给你一个二维平面,你需要在其上放置 nn 个棋子。

你只能将棋子放在整数坐标的点上。将棋子放在坐标点 (x,y) (x, y) 上的成本等于 ∣x∣+∣y∣ |x| + |y| (其中,∣a∣|a| 表示 aa 的绝对值),放置 nn 个棋子的成本等于其中成本最大的单个棋子的成本。

你需要在平面上放置 nn 个棋子,使得每对棋子之间的欧几里得距离严格大于 11,且最终的成本尽可能小,而你需要计算这个最小成本。

输入格式

第一行包含一个整数 tt(1≤t≤1041 \leq t \leq 10^4),表示测试数据组数。

接下来 tt 行,每行包含一个整数 nn (1≤n≤10181 \leq n \leq 10^{18}),表示需要放置的棋子数量。

输出格式

对于每个测试用例,输出一个整数,表示在每对棋子之间的欧几里得距离严格大于 11 的前提下放置 nn 个棋子的最小成本。不同测试用例的输出之间以换行隔开。

样例 #1

样例输入 #1

4
1
3
5
975461057789971042

样例输出 #1

0
1
2
987654321

样例 11 解释

在第一个测试用例中,你可以把唯一的棋子放在坐标 (0,0) (0, 0) 上,总成本为 0+0=0 0 + 0 = 0 。

在第二个测试用例中,你可以将棋子放在 (−1,0) (-1, 0) ,(0,1) (0, 1) 和 (1,0) (1, 0) 上,成本分别为 ∣−1∣+∣0∣=1 |-1| + |0| = 1 ,∣0∣+∣1∣=1 |0| + |1| = 1 和 ∣0∣+∣1∣=1 |0| + |1| = 1 。每对棋子之间的距离严格大于 11(例如,(−1,0)(-1,0) 和 (0,1) (0,1) 之间的距离等于 2 \sqrt{2} )。总成本等于 max⁡(1,1,1)=1 \max(1,1,1)=1 。

在第三个测试用例中,你可以将棋子放在 (−1,−1) (-1,-1) ,(−1,1) (-1,1) ,(1,1) (1,1) ,(0,0) (0,0) 和 (0,2) (0,2) 上。总成本等于 max⁡(2,2,2,0,2)=2 \max(2, 2, 2, 0, 2) = 2 。