CF1550A.Find The Array

Let's call an array $a$ consisting of $n$ positive (greater than $0$) integers beautiful if the following condition is held for every $i$ from $1$ to $n$: either $a_i = 1$, or at least one of the numbers $a_i - 1$ and $a_i - 2$ exists in the array as well.

For example:

• the array $[5, 3, 1]$ is beautiful: for $a_1$, the number $a_1 - 2 = 3$ exists in the array; for $a_2$, the number $a_2 - 2 = 1$ exists in the array; for $a_3$, the condition $a_3 = 1$ holds;
• the array $[1, 2, 2, 2, 2]$ is beautiful: for $a_1$, the condition $a_1 = 1$ holds; for every other number $a_i$, the number $a_i - 1 = 1$ exists in the array;
• the array $[1, 4]$ is not beautiful: for $a_2$, neither $a_2 - 2 = 2$ nor $a_2 - 1 = 3$ exists in the array, and $a_2 \ne 1$;
• the array $[2]$ is not beautiful: for $a_1$, neither $a_1 - 1 = 1$ nor $a_1 - 2 = 0$ exists in the array, and $a_1 \ne 1$;
• the array $[2, 1, 3]$ is beautiful: for $a_1$, the number $a_1 - 1 = 1$ exists in the array; for $a_2$, the condition $a_2 = 1$ holds; for $a_3$, the number $a_3 - 2 = 1$ exists in the array.

You are given a positive integer $s$. Find the minimum possible size of a beautiful array with the sum of elements equal to $s$.

我们称一个由 $n$ 个正整数（即大于 $0$ 的整数）构成的数组 $a$ 是优美的，如果对每个从 $1$ 到 $n$ 的下标 $i$，以下条件之一成立：

• $a_i = 1$，或
• $a_i - 1$ 和 $a_i - 2$ 中至少有一个也出现在该数组中。

例如：

• 数组 $[5, 3, 1]$ 是优美的：对 $a_1$，$a_1 - 2 = 3$ 在数组中存在；对 $a_2$，$a_2 - 2 = 1$ 在数组中存在；对 $a_3$，满足 $a_3 = 1$；
• 数组 $[1, 2, 2, 2, 2]$ 是优美的：对 $a_1$，满足 $a_1 = 1$；对其他每个 $a_i$，$a_i - 1 = 1$ 均在数组中存在；
• 数组 $[1, 4]$ 不是优美的：对 $a_2$，$a_2 - 2 = 2$ 和 $a_2 - 1 = 3$ 均不在数组中，且 $a_2 \ne 1$；
• 数组 $[2]$ 不是优美的：对 $a_1$，$a_1 - 1 = 1$ 和 $a_1 - 2 = 0$ 均不在数组中，且 $a_1 \ne 1$；
• 数组 $[2, 1, 3]$ 是优美的：对 $a_1$，$a_1 - 1 = 1$ 在数组中存在；对 $a_2$，满足 $a_2 = 1$；对 $a_3$，$a_3 - 2 = 1$ 在数组中存在。

给定一个正整数 $s$。求元素和恰好为 $s$ 的优美数组的最小可能长度。

The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.

Then $t$ lines follow, the $i$-th line contains one integer $s$ ($1 \le s \le 5000$) for the $i$-th test case.

第一行包含一个整数 $t$（$1 \le t \le 5000$）—— 测试用例的数量。

接下来有 $t$ 行，其中第 $i$ 行包含一个整数 $s$（$1 \le s \le 5000$），表示第 $i$ 个测试用例的输入。

Print $t$ integers, the $i$-th integer should be the answer for the $i$-th testcase: the minimum possible size of a beautiful array with the sum of elements equal to $s$.

输出 $t$ 个整数，其中第 $i$ 个整数应为第 $i$ 个测试用例的答案：元素和等于 $s$ 的优美数组的最小可能长度。

Consider the example test:

1. in the first test case, the array $[1]$ meets all conditions;
2. in the second test case, the array $[3, 4, 1]$ meets all conditions;
3. in the third test case, the array $[1, 2, 4]$ meets all conditions;
4. in the fourth test case, the array $[1, 4, 6, 8, 10, 2, 11]$ meets all conditions.

考虑以下示例测试：

1. 在第一个测试用例中，数组 $[1]$ 满足所有条件；
2. 在第二个测试用例中，数组 $[3, 4, 1]$ 满足所有条件；
3. 在第三个测试用例中，数组 $[1, 2, 4]$ 满足所有条件；
4. 在第四个测试用例中，数组 $[1, 4, 6, 8, 10, 2, 11]$ 满足所有条件。