Find The Array

题意翻译

一个数组 $a$ 是好的当且仅当数组内每一个数 $a_i$ 满足： - $a_i = 1$ - $a_i - 1 \in a$ - $a_i - 2 \in a$ 其中之一。现在给出一个好的数组 $a$ 的元素和 $S$，询问 $a$ 数组最少有几个数。

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

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 $ .

输入输出样例

输入样例 #1

4
1
8
7
42

输出样例 #1

1
3
3
7

说明

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.