# C. Increase and Copy SOLUTION CODEFORCES

Page Contents

## Increase and Copy SOLUTION

Initially, you have the array a consisting of one element 1 (a=).

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