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 s1 {
	public static void main(String[] args) throws Exception {
		FastScanner scan=new FastScanner(System.in);
		PrintWriter out=new PrintWriter(System.out);

//		int T=1;
		int T=scan.nextInt();
		while(T-->0) {

			int s=scan.nextInt(),ans=0,j=0;
			for(int i=1;s-i>=0;i+=2) {
				ans++;
				s-=i;
				j=i;
			} for(int i=j+1;i>=0&&s>0;i--) {
				while(s-i>=0) {
					s-=i;
					ans++;
				}
			} out.println(ans);

		} out.close();
	}
}

class Pair {
	Integer a,b;
	Pair(int a,int b) {
		this.a=a;
		this.b=b;
	}
}

class FastScanner {
	private InputStream stream;
	private byte[] buf=new byte[1024];
	private int curChar;
	private int numChars;

	public FastScanner(InputStream stream) { this.stream=stream; }

	int read() {
		if(numChars==-1) throw new InputMismatchException();
		if(curChar>=numChars) {
			curChar=0;
			try { numChars=stream.read(buf); }
			catch(IOException e) { throw new InputMismatchException(); }
			if(numChars<=0) return -1;
		} return buf[curChar++];
	}

	boolean isSpaceChar(int c) { return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1; }

	boolean isEndline(int c) { return c=='\n'||c=='\r'||c==-1; }

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

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

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

	String next() {
		int c=read();
		while(isSpaceChar(c)) c=read();
		StringBuilder res=new StringBuilder();
		do {
			res.appendCodePoint(c);
			c=read();
		} while(!isSpaceChar(c));
		return res.toString();
	}

	String nextLine() {
		int c=read();
		while(isEndline(c)) c=read();
		StringBuilder res=new StringBuilder();
		do {
			res.appendCodePoint(c);
			c=read();
		} while(!isEndline(c));
		return res.toString();
	}
}