最初,数组 $$$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