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.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;

public class Solution {
  // @formatter:off
  private static final String inputPath="src/ts2_input.txt", expectedPath="src/ts2_output.txt", outputPath="src/ts2_ans.txt";
  private static int readInt() throws Exception {return Integer.parseInt(br.readLine());}
  private static long readLong() throws Exception {return Long.parseLong(br.readLine());}
  private static int[] readIntArray() throws Exception { String line = br.readLine(); if (line == null || line.isEmpty()) return null; String[] lines = line.split(" "); int n = Integer.parseInt(lines[0]);
    int[] nums = new int[n]; for (int i = 0; i < n; i++) {nums[i] = Integer.parseInt(lines[i + 1]);} return nums; }
  private static int[] readIntArray(int n) throws Exception { int[] nums = new int[n]; String[] lines = br.readLine().split(" "); for (int i = 0; i < n; i++) { nums[i] = Integer.parseInt(lines[i]); } return nums; }
  private static long[] readLongArray(int n) throws Exception { long[] nums = new long[n]; String[] lines = br.readLine().split(" "); for (int i = 0; i < n; i++) { nums[i] = Long.parseLong(lines[i]);} return nums; }
  private static String[] readStringArray(int n) throws Exception { String[] nums = new String[n]; for (int i = 0; i < n; i++) { nums[i] = br.readLine(); } return nums; }
  private static void printArrayInline(int[] nums) throws Exception {for (int i = 0; i < nums.length - 1; i++) {bw.write(nums[i] + " ");}bw.write(nums[nums.length - 1] + "\n");}
  private static void printArrayInline(long[] nums) throws Exception {for (int i = 0; i < nums.length - 1; i++) {bw.write(nums[i] + " ");}bw.write(nums[nums.length - 1] + "\n");}
  private static <T> void printListInLine(List<T> nums) throws Exception {for (int i = 0; i < nums.size() - 1; i++) {bw.write(nums.get(i).toString() + " ");} bw.write(nums.get(nums.size() - 1) + "\n");}
  private static <T> void printListMultiLine(List<T> nums) throws Exception {for (T num : nums) bw.write(num.toString() + "\n");}
  private static void printArrayMultiLine(int[] nums) throws Exception {for (int num : nums) bw.write(num + "\n");}
  private static int parseInt(String str) { return Integer.parseInt(str); }
  private static int parseInt(String[] str, int i) { return Integer.parseInt(str[i]); }
  private static long parseLong(String str) { return Long.parseLong(str);}
  private static long parseLong(String[] str, int i) {return Long.parseLong(str[i]);}
  private static int[] makeRandomArray(int size, int lower, int upper) {Random random = new Random(System.currentTimeMillis());int[] nums = new int[size];for (int i = 0; i < size; i++) {nums[i] = random.nextInt(upper - lower + 1) + lower;}return nums;}
  private static long[] makeRandomLongArray(int size, int lower, int upper) {Random random = new Random(System.currentTimeMillis());long[] nums = new long[size];for (int i = 0; i < size; i++){nums[i] = random.nextInt(upper - lower + 1) + lower;}return nums;}
  private List<Integer>[] makeGraph(int n) {List<Integer>[] graph = new ArrayList[n];for(int i = 0; i < n; i ++) {graph[i] = new ArrayList<>();}return graph;}
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static PrintWriter bw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  //static { try { String env = System.getProperty("env-jay"); if (env != null && env.equals("jay")) { br = new BufferedReader(new FileReader(inputPath)); bw = new PrintWriter(new BufferedWriter(new FileWriter(outputPath, false))); }} catch (Throwable e) {}}
  private static void test() throws Exception {
    try {String env = System.getProperty("env-jay");if (env != null && env.equals("jay")) {List<String> output = Files.readAllLines(Paths.get(outputPath), StandardCharsets.UTF_8);List<String> expected = Files.readAllLines(Paths.get(expectedPath), StandardCharsets.UTF_8);
      for(int line = 0; line < Math.max(output.size(), expected.size()); line ++) {if(line == output.size()) {System.err.println(String.format("Line[%d], There is no extra guess.\nExpected:[%s]", line, expected.get(line)));System.exit(-1);}
        if (line == expected.size()) {System.err.println(String.format( "Line[%d], There is no guess.\nOutput:[%s]" , line + 1, output.get(line))); System.exit(-1);}String ans = expected.get(line), guess = output.get(line);
        if (!ans.equals(guess)) {System.err.println(String.format("Line[%d], Wrong guess.\nAnswer:[%s]\nGuess:[%s]", line + 1, ans, guess));System.exit(-2);}}}} catch (Throwable e) {}}
  // @formatter:on

  public static void main(String[] args) throws Exception {
    int testCases = readInt();
    for (int iter = 1; iter <= testCases; iter++) {
      int s = readInt();
      bw.println(solve(s));
    }
    bw.flush();
    bw.close();
    br.close();
    //test();
  }

  private static int solve(int target) {
    int count = 1;
    target -= 1;
    int min = 1;
    int max = 1;
    while(target != 0) {
      if(target == max + 1) {
        target -= max + 1;
        max ++;
        count ++;
      } else if (target >= max + 2) {
        target -= max + 2;
        max += 2;
        count ++;
      } else {
        target -= target;
        count++;
      }
    }
    return count;
  }
}