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

Input

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

Then t lines follow, the i-th line contains one integer s (1 ≤ s ≤ 5000) for the i-th test case.

Output

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.

Example

Input


4
1
8
7
42


Output


1
3
3
7

Note

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. 


#----------------INPUT READERS------------------#
def readInteger():
    return int(input())

def readString():
    return input()

def readMultipleIntegers():
    return map(int, input().split(' '))
 
def readMultipleIntegersList():
    return list(readMultipleIntegers())

def readMultipleWordsInStringList():
    return list(input().split())


#---------------------CHARACTER TO INT AND VICE VERSA--------------------------#
def charToInt(c):
    return ord(c)

def intToChar(x):
    return chr(x)

def lowerCaseAlphabetsList():
    temp=[chr(i) for i in range(97,123)]
    return temp

def upperCaseAlphabetsList():
    temp=[chr(i) for i in range(65,91)]
    return temp


#-------------OTHER UTILITIES--------------#

def listToDictionary(l):
    d={}
    for i in l:
        if i not in d:
            d[i]=1
    return d

def listToSet(l):
    return set(l)

def gcd(a,b):
    
    if (b == 0):
         return a
    return gcd(b, a%b)

def lcm(a,b):
    return (a / gcd(a,b))* b

#def primesUptoX(x):



#----------------FUNCTIONS FOR PARTICULAR QUESTIONS----------------#
import math
def solve(s):
    count=2
    sm=4
    i=5
    while sm<s:
        if sm+i<=s or sm+i-1<=s:
            sm+=i
            i+=2
            count+=1
        else:
            i-=2
    return count
            


#--------------DRIVER CODE---------------#
for _ in range(readInteger()):
    s=readInteger()
    if s==1:
        print(1)
        continue
    if s<4:
        print(2)
        continue
    
    print(solve(s))