题目描述
给你一个二维平面,你需要在其上放置 n 个棋子。
你只能将棋子放在整数坐标的点上。将棋子放在坐标点 (x,y) 上的成本等于 ∣x∣+∣y∣ (其中,∣a∣ 表示 a 的绝对值),放置 n 个棋子的成本等于其中成本最大的单个棋子的成本。
你需要在平面上放置 n 个棋子,使得最终的成本尽可能小,而你需要计算这个最小成本。
输入格式
第一行包含一个整数 t(1≤t≤104),表示测试数据组数。
接下来 t 行,每行包含一个整数 n (1≤n≤1018),表示需要放置的棋子数量。
输出格式
对于每个测试用例,输出一个整数,表示放置 n 个棋子的最小成本。不同测试用例的输出之间以换行隔开。
样例 #1
样例输入 #1
4
1
3
5
975461057789971042
样例输出 #1
0
1
1
698377068
样例 1 解释
在第一个测试用例中,你可以把唯一的棋子放在坐标 (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)之间的距离等于 2)。总成本等于 max(1,1,1)=1。
在第三个测试用例中,你可以将棋子放在 (0,−1),(0,1),(1,0),(−1,0) 和 (0,0) 上。总成本等于 max(1,1,1,1,0)=1。