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 (single) element of $a$ by $1$ (choose some $i$ from $1$ to the current length of $a$ and increase $a_i$ by one);  Append the copy of some (single) element of $a$ to the end of the array (choose some $i$ from $1$ to the current length of $a$ and append $a_i$ to the end of the array). 

For example, consider the sequence of five moves:

  You take the first element $a_1$, append its copy to the end of the array and get $a = [1, 1]$.  You take the first element $a_1$, increase it by $1$ and get $a = [2, 1]$.  You take the second element $a_2$, append its copy to the end of the array and get $a = [2, 1, 1]$.  You take the first element $a_1$, append its copy to the end of the array and get $a = [2, 1, 1, 2]$.  You take the fourth element $a_4$, 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 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($1 \le n \le 10^9$) — 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-----
Input
5
1
5
42
1337
1000000000

Output
0
3
11
72
63244

Difficulty: introductory

Starter code:

Solutions:
import math
for _ in range(int(input())):
    n=int(input())
    if n==1:
        print(0)
    else:
        k=int(n**(0.5))
        if k*k<n:
            k+=1
        # print(n,k)    
        ans=k-1
        if k*(k-1)>=n:
            ans+=(k-2)
        else:
            ans+=(k-1)
        print(ans)    

import math
# x increases: x + ceil(n/(x+1)) - 1


t = int(input())

for _ in range(t):
    n = int(input())
    
    s = int(n**0.5)
    
    cands = list(range(max(0, s-100), s+100))
    
    ans = min(x+math.ceil(n/(x+1))-1 for x in cands)
    print(ans)
    
    


from math import ceil
for _ in range(int(input())):
    n = int(input())
    x = (ceil((n ** 0.5)))
    if n <= x * (x - 1):
        print(x + x - 1 - 2)
    else:
        print(2 * x - 2)

from sys import stdin

tt = int(stdin.readline())

for loop in range(tt):

    n = int(stdin.readline())

    x = int(n**0.5)
    ans = float("inf")

    for i in range(x-10,x+10):

        for j in range(x-10,x+10):

            if i > 0 and j > 0 and i*j >= n:
                ans = min(ans , i+j-2)

    print (ans)

# Created by: WeirdBugsButOkay
# 28-09-2020, 13:44:16

import math

def ceil(a, b) :
    return (a + b - 1) // b

def calc(n, a) :
    return (a - 1 + ceil(n - a, a))

def solve() :
    n = int(input())
    i = int(math.sqrt(n))
    ans = n - 1
    ans = min(ans, calc(n, i))
    ans = min(ans, calc(n, i + 1))
    print(ans)

t = 1
t = int(input())
for _ in range (0, t) :
    solve()


a=int(input())
from math import sqrt
for i in range(a):
    b=int(input())
    g=int(sqrt(b))
    if b!=1:
        ans=g-1
        if b%g==0:
            ans+=b//g-1
        else:
            ans+=b//g
        print(ans)
    else:print(0)


for _ in range (int(input())):
    a=int(input())
    ans=100000
    for i in range(40000):
        t=i+(a//(i+1))
        if(a%(i+1)==0):t=t-1
        if(t<ans):ans=t
    if(a==1):ans=0
    print(ans)

T = int(input())

def copy(N):
    
    Max = 1
    
    Min = n
    
    while Max*Max <= N:
        
        Min = min(Min, Max - 1 + N//Max - 1 + min(1, N%Max))
        
        Max += 1
        
    return Min
    
for i in range(T):
    
    n = int(input())
    
    print(copy(n))

3
import sys
input = lambda: sys.stdin.readline().strip()
for _ in range(int(input())):
    n = int(input())
    print(min(i - 1 + (n + i - 1) // i - 1 for i in range(1, int(n ** 0.5) + 10)))


import math
for i in range(int(input())):
	n = int(input())
	st = int(math.sqrt(n))
	mi = n
	for x in range(max(0, st - 100), st + 100):
		cur = ((n + x) // (x + 1)) + x - 1
		mi = min(cur, mi)
	print(mi)

import math
def solve():
    n= int(input())
    k = int(math.sqrt(n))
    if k * k == n:
        print(k * 2 - 2)
    elif k * (k + 1) >= n:
        print(k * 2 - 1)
    else:
        print(k * 2)
for i in range(int(input())):
    solve()

# -*- coding: utf-8 -*-
"""
Created on Mon Sep 28 14:20:28 2020

@author: Dark Soul
"""
import math
t=int(input(''))
for _ in range(t):
    n=int(input(''))
    x=math.sqrt(n)
    if x==int(x):
        x=int(x)
        sol=(n//x)-1
        sol+=(x-1)
        print(sol)
    else:
        x=int(x)+1
        sol=n//x
        if sol*x==n:
            sol-=1
        sol+=(x-1)
        print(sol)
        


t = int(input())
while t:
    t += -1
    ans = 999999999999
    n = int(input())
    s = 1
    while 1:
        tmp = n // s + bool(n % s) - 1 + (s - 1)
        if tmp > ans: break
        ans = tmp
        s -= -1
    print(ans)

T, = list(map(int, input().split()))
for _ in range(T):
    N, = list(map(int, input().split()))
    c = int(N**0.5)
    R = 10**18
    for i in range(max(1, c-10), c+10):
        R = min(R, i-(-N//i)-2)
    print(R)


import math
for _ in range(int(input())):
    n=int(input())
    x=int(math.sqrt(n))
    ans=n//x

    if(n%x!=0):
        ans+=1
    x-=1
    ans+=x
    print(ans-1)

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) ]))
def invr():
    return(list(map(int,input().split())))

n = inp()

for i in range(n):
    val = inp()

    cnt = 1
    prev = 10**10
    while(True):
        if((val+cnt-1) // cnt + cnt - 1  > prev):
            print(prev - 1)
            break
        else:
            prev = (val+cnt-1) // cnt + cnt - 1
            #print(prev)
            cnt += 1


for __ in range(int(input())):
    n = int(input())
    ans = 10 ** 9
    for i in range(1, min(n, 10 ** 5)):
        ans = min(i - 1 + (n - 1) // i, 10 ** 6, ans)
    if ans == 10 ** 9:
        ans = 0
    print(ans)

import math
t=int(input())
for you in range(t):
    n=int(input())
    z=int(math.sqrt(n))
    l=[z-1,z-2,z,z+1,z+2]
    mina=10**18
    for i in l:
        if(i>0):
            mina=min(mina,i+(n+i-1)//i-2)
    print(mina)


t = int(input())
import math as m

for test in range(1, t+1):
    n = int(input())
    x = int(n**0.5)-1
    y = m.ceil(n/(x+1))
    print(x+y-1)


from math import ceil
for tc in range(int(input())):
    n = int(input())
    s = ceil(n ** 0.5)
    t = (n ** 0.5) // 1
    sans = ceil(n / s) + s
    tans = ceil(n / t) + t
    print(max(min(sans, tans) - 2, 0))