C. Increase and Copy SOLUTION CODEFORCES

Increase and Copy SOLUTION

Initially, you have the array a consisting of one element 1 (a=[1]).
 
In one move, you can do one of the following things:
 
Increase some element of a by 1 (choose some i from 1 to the current length of a and increase ai by one);
Append the copy of some element of a to the end of the array (choose some i from 1 to the current length of a and append ai to the end of the array).
For example, consider the sequence of five moves:
 
You take the first element a1, append its copy to the end of the array and get a=[1,1].
You take the first element a1, increase it by 1 and get a=[2,1].
You take the second element a2, append its copy to the end of the array and get a=[2,1,1].
You take the first element a1, append its copy to the end of the array and get a=[2,1,1,2].
You take the fourth element a4, increase it by 1 and get a=[2,1,1,3].
Your task is to find the minimum number of moves required to obtain the array with the sum at least n.
 
You have to answer t independent test cases.
 
Input
The first line of the input contains one integer t (1≤t≤1000) — the number of test cases. Then t test cases follow.
 
The only line of the test case contains one integer n (1≤n≤109) — the lower bound on the sum of the array.
 
Output
For each test case, print the answer: the minimum number of moves required to obtain the array with the sum at least n.
 
Example
inputCopy
5
1
5
42
1337
1000000000
outputCopy
0
3
11
72
63244
 

Leave a Comment

close
error: Content is protected !!