← 返回题目列表

Codeforces · 1426/C

C. 增加和复制

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

最初,数组 $$$a$$$ 由一个元素 $$$1$$$ ($$$a = [1]$$$) 组成。

在一步操作中,您可以执行以下操作之一:

- 将$$$a$$$的某些(单个)元素增加$$$1$$$(从$$$1$$$中选择一些$$$i$$$到$$$a$$$的当前长度,并将$$$a_i$$$增加1);
- 将 $$$a$$$ 的某些(单个)元素的副本附加到数组末尾(从 $$$1$$$ 中选择一些 $$$i$$$ 到 $$$a$$$ 的当前长度,并将 $$$a_i$$$ 附加到数组末尾)。

例如,考虑五个动作的顺序:

1. 获取第一个元素 $$$a_1$$$,将其副本附加到数组末尾并得到 $$$a = [1, 1]$$$。
2. 将第一个元素 $$$a_1$$$ 增加 $$$1$$$ 并得到 $$$a = [2, 1]$$$。
3. 获取第二个元素 $$$a_2$$$,将其副本附加到数组末尾并得到 $$$a = [2, 1, 1]$$$。
4. 获取第一个元素 $$$a_1$$$,将其副本附加到数组末尾并得到 $$$a = [2, 1, 1, 2]$$$。
5. 将第四个元素 $$$a_4$$$ 增加 $$$1$$$ 并得到 $$$a = [2, 1, 1, 3]$$$。

你的任务是找到获得总和至少为 $$$n$$$ 的数组所需的最少移动次数。

您必须回答 $$$t$$$ 独立测试用例。

输入

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

测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$) — 数组总和的下限。

输出

对于每个测试用例,打印答案:获得总和至少为 $$$n$$$ 的数组所需的最小移动次数。

示例

输入 #1

5
1
5
42
1337
1000000000

输出 #1

0
3
11
72
63244