← 返回题目列表

Codeforces · 1862/D

D. 冰淇淋球

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

Tema 决定提高他的冰淇淋制作技能。他已经学会了如何使用两个球制作圆锥形冰淇淋。

在迷恋冰淇淋之前,特马对数学感兴趣。因此,他很好奇要制作 $$$n$$$ 不同类型的冰淇淋所需的最少球数。

有很多可能的冰淇淋口味:$$$1, 2, 3, \dots$$$。 Tema 可以制作任何口味的双球冰淇淋(可能相同)。

如果两种冰淇淋的球口味不同,则认为它们不同。例如,$$$\{1, 2\} = \{2, 1\}$$$,但 $$$\{1, 1\} \neq \{1, 2\}$$$。

例如,有以下冰淇淋球:$$$\{1, 1, 2\}$$$,Tema 只能制作两种类型的冰淇淋:$$$\{1, 1\}$$$ 和 $$$\{1, 2\}$$$。

请注意,Tema 不需要同时制作所有蛋卷冰淇淋。这意味着他独立制作蛋卷冰淇淋。另外,为了为某些 $$$x$$$ 制作以下圆锥体 $$$\{x, x\}$$$,Tema 至少需要 $$$2$$$ 类型的 $$$x$$$ 球。

帮助特马回答这个问题。可以证明答案总是存在的。

输入

每个测试由多个测试用例组成。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — Tema 想要制作的冰淇淋类型的数量。

输出

对于每个测试用例,输出一个整数 - Tema 需要购买的最小球数。

示例

输入 #1

5
1
3
6
179
1000000000000000000

输出 #1

2
3
4
27
2648956421

注意

在第一个示例中,具有以下球类型就足够了:$$$\{1, 1\}$$$。请注意,设置 $$$\{1\}$$$ 如果不够,因为我们至少需要 $$$2$$$ 类型为 $$$1$$$ 的球才能制作这样的圆锥体 $$$\{1, 1\}$$$。

在第二个示例中,不可能用 $$$2$$$ 球来制作,但可以用这些球来制作:$$$\{1, 2, 3\}$$$。

在第三个样本中, $$$\{1, 2, 3, 4\}$$$ 是最佳答案,因此我们可以得到以下蛋卷冰淇淋: $$$\{1, 2\}$$$, $$$\{1, 3\}$$$, $$$\{1, 4\}$$$, $$$\{2, 3\}$$$, $$$\{2, 4\}$$$, $$$\{3, 4\}$$$。