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. 


import java.io.*;
import java.sql.Array;
import java.util.*;


public class Main {
    static int cnt[][] = new int[100001][2];

    /************************ SOLUTION STARTS HERE ************************/
    private static void solve() {
        int t = nextInt();
        while(t-- > 0) {
            int n = nextInt();
            if(n == 1)
                println(1);
            else {
                int sqrt = (int)Math.sqrt(n);
                if(sqrt*sqrt == n)
                    println(sqrt);
                else
                    println(sqrt + 1);
            }

        }

    }


    /************************ SOLUTION ENDS HERE ************************/



    /************************ TEMPLATE STARTS HERE **********************/

    public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
        st = null;
        solve();
        reader.close();
        writer.close();
    }

    static BufferedReader  reader;
    static PrintWriter     writer;
    static StringTokenizer st;

    static String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = reader.readLine();
                if (line == null) {
                    return null;
                }
                st = new StringTokenizer(line);
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
        return st.nextToken();
    }

    static String nextLine() {
        String s = null;
        try {
            s = reader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    static int nextInt() {
        return Integer.parseInt(next());
    }

    static long nextLong() {
        return Long.parseLong(next());
    }

    static double nextDouble() {
        return Double.parseDouble(next());
    }

    static char nextChar() {
        return next().charAt(0);
    }

    static int[] nextIntArray(int n) {
        int[] a = new int[n];
        int i = 0;
        while (i < n) {
            a[i++] = nextInt();
        }
        return a;
    }

    static long[] nextLongArray(int n) {
        long[] a = new long[n];
        int i = 0;
        while (i < n) {
            a[i++] = nextLong();
        }
        return a;
    }

    static int[] nextIntArrayOneBased(int n) {
        int[] a = new int[n + 1];
        int i = 1;
        while (i <= n) {
            a[i++] = nextInt();
        }
        return a;
    }

    static long[] nextLongArrayOneBased(int n) {
        long[] a = new long[n + 1];
        int i = 1;
        while (i <= n) {
            a[i++] = nextLong();
        }
        return a;
    }

    static void print(Object o) {
        writer.print(o);
    }

    static void println(Object o) {
        writer.println(o);
    }

    static void printArr(int[] arr) {
        for(int i = 0 ; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void exchange(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void shuffle(int arr[], int n) {
        for (int i = 0; i < n; i++) {
            int r = (int)Math.floor(Math.random() * (i+1));
            exchange(arr, i, r);
        }
    }

    /************************ TEMPLATE ENDS HERE ************************/
}
