[数据结构与算法]A. Find The Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's call an array?aa?consisting of?nn?positive (greater than?00) integers?beautiful?if the following condition is held for every?ii?from?11?to?nn: either?ai=1ai=1, or at least one of the numbers?ai?1ai?1?and?ai?2ai?2?exists in the array as well.

For example:

• the array?[5,3,1][5,3,1]?is beautiful: for?a1a1, the number?a1?2=3a1?2=3?exists in the array; for?a2a2, the number?a2?2=1a2?2=1?exists in the array; for?a3a3, the condition?a3=1a3=1?holds;
• the array?[1,2,2,2,2][1,2,2,2,2]?is beautiful: for?a1a1, the condition?a1=1a1=1?holds; for every other number?aiai, the number?ai?1=1ai?1=1?exists in the array;
• the array?[1,4][1,4]?is not beautiful: for?a2a2, neither?a2?2=2a2?2=2?nor?a2?1=3a2?1=3?exists in the array, and?a2≠1a2≠1;
• the array?[2][2]?is not beautiful: for?a1a1, neither?a1?1=1a1?1=1?nor?a1?2=0a1?2=0?exists in the array, and?a1≠1a1≠1;
• the array?[2,1,3][2,1,3]?is beautiful: for?a1a1, the number?a1?1=1a1?1=1?exists in the array; for?a2a2, the condition?a2=1a2=1?holds; for?a3a3, the number?a3?2=1a3?2=1?exists in the array.

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

Input

The first line contains one integer?tt?(1≤t≤50001≤t≤5000) — the number of test cases.

Then?tt?lines follow, the?ii-th line contains one integer?ss?(1≤s≤50001≤s≤5000) for the?ii-th test case.

Output

Print?tt?integers, the?ii-th integer should be the answer for the?ii-th testcase: the minimum possible size of a beautiful array with the sum of elements equal to?ss.

Example

input

Copy

4
1
8
7
42

output

Copy

1
3
3
7

Note

Consider the example test:

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

解题说明：此题采用贪心算法，每个数组必定有1，在确保最少数量时需要塞入一些大数，所以一开始从1不断塞入 += 2 的数，同时每塞入一个数就减小目标 n 的值，直到小于0。

#include<stdio.h>

int main()
{
	int t, i, a, j;
	scanf("%d", &t);
	for (i = 1; i <= t; i++)
	{
		scanf("%d", &a);
		for (j = 0; a>0; j++) 
		{
			a -= 2 * j + 1;
		}
		printf("%d\n", j);
	}
	return 0;
}