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. 
# A . Floor Number (Accepted)
'''
import math
def Test_case_le_na(Test_cases):
    Resultant_list = []
    for i in range(0 , Test_cases):
        str_n , str_x = input().split()
        n = int(str_n)
        x = int(str_x)
        if n < 1 or n > 1000:
            exit()
        if x < 1 or x > 1000:
            exit()
        if n == 1 or n == 2:
            Resultant_list.append(1)
        elif n < x :
            Resultant_list.append(2)
        else:
            # Answer = int (((n + x - 3) / x) + 1) 
            Answer = math.ceil((n - 2) / x) + 1 
            Resultant_list.append(Answer)
    return Resultant_list

Test_cases = int(input())
if Test_cases < 1 or Test_cases > 1000:
    exit()
# We have to find the floor number
Answer_list = Test_case_le_na(Test_cases)
for i in Answer_list:
    print(i)
'''


# A . Robot Program (Accepted)
'''
def solve (Test_cases):
    Resultant_list = []
    for i in range (0 , Test_cases):
        str_x , str_y = input().split()
        x = int(str_x)
        y = int(str_y)
        if x < 0 or x > 10000:
            exit()
        if y < 0 or y > 10000:
            exit()
        # Program starts here 
        if x > y :
            temp = x
            x = y
            y = temp 
        value = 2 * x
        left = y - x
        if left == 0 :
            Resultant_list.append(value)
        else :
            value += 1
            left -= 1
            value += (left * 2)
            Resultant_list.append(value)
    return Resultant_list
Test_cases = int(input())
if Test_cases < 1 or Test_cases > 10000:
    exit()
answer_list = solve(Test_cases) 
for i in answer_list:
    print(i)
'''

# C. Unique Number (Wrong answer in Test_case 2)
'''
def solve(Test_cases):
    Resultant_list = []
    for T in range(Test_cases):
        x = int (input())
        if x < 1 or x > 50 :
            exit()
        flag = 0
        for i in range (0 , 10):
            if flag != 0 :
                break
            if i == x :
                Resultant_list.append(i)
                flag += 1
                break
            else :
                for j in range (0, 10):
                    if i + j == x  and i != j:
                        flag += 1
                        Number = (10 * i) + j
                        Resultant_list.append(Number)
                        break
        if flag == 0 :
            Resultant_list.append(-1)
    return Resultant_list
Test_cases = int (input())
if Test_cases < 1 or Test_cases > 50 :
    exit()
Answer_list = solve(Test_cases)
# print('Ans')
for i in Answer_list : 
    print(i) 
'''

# A . Subtract or Divide (TLE on Test_case 3)
'''
def solve (Test_cases) :
    Resultant_list = []
    for i in range(Test_cases):
        N = int (input())
        if N < 1 or N > pow(10,9):
            exit()
        count = int (0)
        N_temp = N 
        while N_temp != 1 :
            flag = -1
            for i in range(N - 1 , int((N - 1) / 2) , -1):
                if (N_temp % i == 0):
                    flag += 1 
                    N_temp = int (N / i) 
                    print(N_temp)
                    count = count + 1
                    break
            if flag == -1 :
                N_temp = N_temp - 1
                count = count + 1
            N = N_temp
            # print(N)
        Resultant_list.append(count)
    return Resultant_list
Test_cases = int(input())
if Test_cases < 1 or Test_cases > 1000:
    exit()
Result = solve (Test_cases)
# for i in range(Test_cases):
#     print(Result[i])
'''

# Find the Array
import math 
def solve (Test_cases):
    Resultant_list = []
    for i in range(Test_cases):
        N = int(input())
        if N < 1 or N > 5000:
            exit ()
        sum = int (0)
        x = int (1)
        c = 0
        while sum < N:
            sum += x
            x += 2
            c += 1 
        Resultant_list.append(c)
    return Resultant_list

Test_cases = int(input())
if Test_cases < 1 or Test_cases > 5000:
    exit()
Answer = solve(Test_cases)
for i in Answer :
    print(i)
