← 返回题目列表

Codeforces · 1670/D

D. 非常可疑

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

Sehr Sus 是一个无限六边形网格,如下图所示,由 MennaFadali、ZerooCool 和 Hosssam 控制。

他们喜欢等边三角形,并希望通过添加一些直线在网格上创建 $$$n$$$ 等边三角形。这些三角形的内部必须都是空的(换句话说,任何直线或六边形边都不能穿过任何三角形)。

您可以添加与六边形边缘平行的直线。给定 $$$n$$$,要创建至少 $$$n$$$ 所描述的等边三角形,您需要添加的最少线数是多少?

添加两条红线会产生两个新的黄色等边三角形。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{9}$$$) — 所需的等边三角形数量。

输出

对于每个测试用例,打印具有 $$$n$$$ 或更多等边三角形所需的最少行数。

示例

输入 #1

4
1
2
3
4567

输出 #1

2
2
3
83

注意

在第一个和第二个测试用例中只需要 2 行。添加第一条线后,无论添加到何处都不会创建等边三角形。但添加第二条线后,将同时创建两个三角形。

在第三个测试用例中,最少需要 3 行,如下所示。