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 Sol{
//  ************     n==1  ***************** important test case

public static void main(String []args){
int times=ni();while(times-->0){
  int s=ni();
  int i=(int)Math.sqrt(s);
  
  if(i*i==s)out.println(i);
  else out.println(i+1);
}out.close();}

//-----------------Utility--------------------------------------------
 
static int gcd(int a,int b){if(b==0)return a; return gcd(b,a%b);}
 
static int Max=Integer.MAX_VALUE; static long mod=998244353;
 
static int v(char c){return (int)(c-'a')+1;}
 
static long factorial(long n){
   long ans=1l;
   long i=1l;
   while(i<=n){ans*=i;ans%=mod;i++;}
   return ans;
 } 

static long inv(long n){
   return power(n,mod-2);
 }
public static long power(long x, long y )
    {
        //0^0 = 1
        long res = 1L;
        x = x%mod;
        while(y > 0)
        {
            if((y&1)==1)
                res = (res*x)%mod;
            y >>= 1;
            x = (x*x)%mod;
        }
        return res;
    }
 
static class Pair implements Comparable<Pair>{
        int x;int y;
 
        public Pair(int x,int y) {
         
          this.x=x;this.y=y;
        }
        @Override
        public int compareTo(Pair p){return Long.compare(y,p.y);}
        //public int compareTo(Pair p){return id-p.id;}
       }

static class Node{
   Node next;
   int id;int value;
   Node(int id,int value){
      id=this.id;this.value=value;next=null;
   }
 }
 
//----------------------I/O---------------------------------------------
 
static InputStream inputStream = System.in;
static OutputStream outputStream = System.out;
static FastReader in=new FastReader(inputStream);
static PrintWriter out=new PrintWriter(outputStream);
 
static class FastReader 
{ 
  BufferedReader br; 
  StringTokenizer st; 
 
        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
 
  public String next() 
  { 
      while (st == null || !st.hasMoreElements()) 
      { 
          try
          { 
              st = new StringTokenizer(br.readLine()); 
          } 
          catch (IOException  e) 
          { 
              e.printStackTrace(); 
          } 
      } 
      return st.nextToken(); 
  } 
 
  public int nextInt() 
  { 
      return Integer.parseInt(next()); 
  } 
 
  public long nextLong() 
  { 
      return Long.parseLong(next()); 
  } 
 
 public  double nextDouble() 
  { 
      return Double.parseDouble(next()); 
  } 
 
 
  String nextLine() 
  { 
      String str = ""; 
      try
      { 
          str = br.readLine(); 
      } 
      catch (IOException e) 
      { 
          e.printStackTrace(); 
      } 
      return str; 
  } 
}
static int ni() {
        return in.nextInt();
    }
static long nl(){return in.nextLong();}
static String ns(){return in.nextLine();}
 
}