题目描述

给定一个二维平面，你需要在上面放置 $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$ 个芯片的最小总代价。

说明/提示

在第一个测试用例中，你可以将唯一的芯片放在点 $(0, 0)$，总代价为 $0 + 0 = 0$。

在第二个测试用例中，你可以例如将芯片放在 $(-1, 0)$、$(0, 1)$ 和 $(1, 0)$，其代价分别为 $|-1| + |0| = 1$、$|0| + |1| = 1$ 和 $|1| + |0| = 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$。

由 ChatGPT 4.1 翻译

样例

4
1
3
5
975461057789971042

0
1
2
987654321