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.util.*;
import java.io.*;
public class Main {
		static int min;
		static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		public static void main(String[] args) throws IOException  {
			FastReader sc = new FastReader();
			int t = sc.nextInt();
			while( t-- > 0) {
				int sum = sc.nextInt();
				int temp = 1;
				int ans = 1;
				sum--;
				while( sum!= 0) {
					if( sum >= (temp+2)) {
						sum-=(temp+2);
						temp+=2;
						ans++;
					}
					else if( sum >=( temp+1)) {
						sum-=(temp+1);
						temp++;
						ans++;
					}
					else if( sum >= temp) {
						sum-=temp;
						ans++;
					}
					else {
						ans++;
						sum = 0;
					}
				}
				out.println(ans);
			}
			out.flush();
		}
			
		
		public static int[] nextLargerElement(int[] arr, int n)
		{ 
			Stack<Integer> stack = new Stack<>();
	        int rtrn[] = new int[n];
	        rtrn[n-1] = -1;
	        stack.push( n-1);
	        for( int i = n-2 ;i >= 0 ; i--){
	            int temp = arr[i];
	            int lol = -1;
	            while( !stack.isEmpty() && arr[stack.peek()] <= temp){
	            	if(arr[stack.peek()] == temp ) {
	            		lol = stack.peek();
	            	}
	                stack.pop();
	            }
	            if( stack.isEmpty()){
	            	if( lol != -1) {
	            		rtrn[i] = lol;
	            		}
	            	else {
	                rtrn[i] = -1;
	            	}
	            }
	            else{
	            	rtrn[i] = stack.peek();
	            }
	            stack.push( i);
	        }
	        return rtrn;
	    }
		
		static int gcd(int a, int b) {
			if (b == 0)
				return a;
			return gcd(b, a % b);
		}
	 
		static HashMap<Long,Long> primefactor( long n){
			HashMap<Long ,Long> hm = new HashMap<>();
			long temp = 0;
			while( n%2 == 0) {
				temp++;
				n/=2;
	 		 }	
			if( temp!= 0) {
	 			 hm.put( 2L, temp);
	 		 }
	 		 long c = (long)Math.sqrt(n);
	 		 for( long i = 3 ; i <= c ; i+=2) {
	 			 temp = 0;
	 			 while( n% i == 0) {
	 				 temp++;
	 				 n/=i;
	 			 }
	 			 if( temp!= 0) {
	 				 hm.put( i, temp);
	 			 }
	 		 }
	 		 if( n!= 1) {
	 			 hm.put( n , 1L);
	 		 }
	 		 return hm;
	 		// this is the link where i found this method
	 		 // https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
	 	 }
	 
		 static class FastReader {
		        BufferedReader br;
		        StringTokenizer st;
		 
		        public FastReader()
		        {
		            br = new BufferedReader(
		                new InputStreamReader(System.in));
		        }
		        
		        String next()
		        {
		            while (st == null || !st.hasMoreElements()) {
		                try {
		                    st = new StringTokenizer(br.readLine());
		                }
		                catch (IOException e) {
		                    e.printStackTrace();
		                }
		            }
		            return st.nextToken();
		        }
		 
		        int nextInt() { return Integer.parseInt(next()); }
		 
		        long nextLong() { return Long.parseLong(next()); }
		 
		        double nextDouble()
		        {
		            return Double.parseDouble(next());
		        }
		 
		        String nextLine()
		        {
		            String str = "";
		            try {
		                str = br.readLine();
		            }
		            catch (IOException e) {
		                e.printStackTrace();
		            }
		            return str;
		        }
		    }
		
}