Problem: A Pythagorean triple is a triple of integer numbers (a, b, c) such that it is possible to form a right triangle with the lengths of the first cathetus, the second cathetus and the hypotenuse equal to a, b and c, respectively. An example of the Pythagorean triple is (3, 4, 5).

Vasya studies the properties of right triangles, and he uses a formula that determines if some triple of integers is Pythagorean. Unfortunately, he has forgotten the exact formula; he remembers only that the formula was some equation with squares. So, he came up with the following formula: c = a^2 - b.

Obviously, this is not the right formula to check if a triple of numbers is Pythagorean. But, to Vasya's surprise, it actually worked on the triple (3, 4, 5): 5 = 3^2 - 4, so, according to Vasya's formula, it is a Pythagorean triple.

When Vasya found the right formula (and understood that his formula is wrong), he wondered: how many are there triples of integers (a, b, c) with 1 ≤ a ≤ b ≤ c ≤ n such that they are Pythagorean both according to his formula and the real definition? He asked you to count these triples.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Each test case consists of one line containing one integer n (1 ≤ n ≤ 10^9).

Output

For each test case, print one integer — the number of triples of integers (a, b, c) with 1 ≤ a ≤ b ≤ c ≤ n such that they are Pythagorean according both to the real definition and to the formula Vasya came up with.

Example

Input


3
3
6
9


Output


0
1
1

Note

The only Pythagorean triple satisfying c = a^2 - b with 1 ≤ a ≤ b ≤ c ≤ 9 is (3, 4, 5); that's why the answer for n = 3 is 0, and the answer for n = 6 (and for n = 9) is 1.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;
import static java.util.Collections.*;
import static java.util.Arrays.*;
public class C<Array, Target> {
    public static int swap(int... args) {
        return args[0];
    }
    //  static Scanner sc = new Scanner(System.in);
    static FastReader sc = new FastReader();
    public static void main(String[] args) throws IOException {
        do {
            startTime = currentTimeMillis();
            //setOut(new PrintStream("output"));
            //setIn(new FileInputStream("input"));
            int T = sc.nextInt();while (T-- != 0)
            {
                solve();

            }
            endTime = currentTimeMillis();
            long duration = endTime - startTime;
            //out.println(duration);
            if (false) {
                out.println(max(3, 2));
                Integer[] ARRAY = new Integer[2];
                ArrayList<Integer> LIST = new ArrayList<>();
                LIST.add(2);
                // sort(LIST, reverseOrder());
                LIST.sort(reverseOrder());
                sort(ARRAY, reverseOrder());
                out.println(LIST + " " + Arrays.toString(ARRAY));
            }
        } while (LOCAL);
    }
    public static boolean isPal(String s)
    {
        StringBuilder stringBuilder = new StringBuilder(s);
        return s.equals(stringBuilder.reverse().toString());
    }
    public static void solve() throws IOException {
        C main = new C<>();
/////////////////////////////////////////////////////////////////////
        int n =sc.nextInt();
        int cn= 0;
        for (int i = 3; i*i/2+1 <=n; i+=2) {
            cn++;
        }
        out.println(cn);
///////////////////////////////////////////////////////////////////////
    }
    public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;
    // public static final boolean LOCAL = System.getProperty("LOCAL")!=null;
    public static final String ANSI_RED = "\u001B[31m";
    public static final String ANSI_RESET = "\u001B[0m";
    static long startTime;
    static long endTime;
    static boolean[] prime;
    static final int M = (int) 1e9 + 7;
    static final long MM = (long) M * M;
    static final int MAX = Integer.MAX_VALUE;
    static final int MIN = Integer.MIN_VALUE;
    static final int SIZE = (int) 1e9 * 2;
    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;
        }
    }
    static class Pair implements Comparable<Pair> {
        private int key;
        private int value;
        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public int second() {
            return value;
        }
        @Override
        public int compareTo(Pair o) {
            return -Integer.compare(key, o.key);
        }
        @Override
        public String toString() {
            return "Pair{" + "x=" + key + ", y=" + value + '}';
        }
    }
    int count(Array[] array, Target target){
        int cn=0;
        for (Array value : array) {
            if (value.equals(target)) cn++;
        }
        return cn;
    }
    static int count (String string , char target){
        int cn=0;
        for (int i = 0; i < string.length(); i++) {
            if(string.charAt(i)==target)cn++;
        }
        return cn;
    }
    void revArray(Array [] arr) {
        int n = arr.length;
        for (int i = 0; i < n / 2; i++) {
            Array temp = arr[i];
            arr[i] = arr[n - i - 1];
            arr[n - i - 1] = temp;
        }
    }
    void printArray(Array [] arr) {
        int n = arr.length;
        for (Array array : arr)out.print(array + " ");
        out.println();
    }
    static void yes() {out.println("YES");}
    static void no() {out.println("NO");}
    public static int lowerBound(Integer[] array, int length, int value) {
        int low = -1;
        int hi = length;
        while (low + 1 < hi) {
            int mid = (low + hi) / 2;
            if (array[mid] <= value) {
                low = mid;
            } else {
                hi = mid;
            }
        }
        return low;
    }
    public static int upperBound(Integer[] array, int length, int value) {
        int low = -1;
        int hi = length;
        while (low + 1 < hi) {
            int mid = (low + hi) >> 1;
            if (array[mid] >= value) {
                hi = mid;
            } else low = mid;
        }
        return hi;
    }
    public static int binarySearch(Integer[] arr, int length, int value) {
        int low = 0;
        int hi = length - 1;
        int ans = -1;
        while (low <= hi) {
            int mid = (low + hi) >> 1;
            if (arr[mid] > value) {
                hi = mid - 1;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                ans = mid;
                break;
            }
        }
        return ans;
    }
    public static int gcd(int a, int b) {
        return b==0?a:gcd(b, a % b);
    }
    public static long lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
    public static int countDivs(int n) {
        int cn = 0;
        int sqr = (int) Math.sqrt(n);
        for (int i = 1; i <= sqr; ++i) {
            if (n % i == 0) {
                ++cn;
            }
        }
        cn *= 2;
        if (sqr * sqr == n) cn--;
        return cn;
    }

    static void prime(int x) {
        //sieve algorithm. nlog(log(n)).
        prime = new boolean[(x + 1)];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int i = 2; i * i <= x; i++)
            if (prime[i])
                for (int j = i * i; j <= x; j += i)
                    prime[j] = false;
    }
    static boolean isEven(long x) {
        return x % 2 == 0;
    }
    static boolean isPrime(long x) {
        boolean flag = true;
        int sqr = (int) Math.sqrt(x);
        if (x < 2) return false;
        for (int i = 2; i <= sqr; i++) {
            if (x % i == 0) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    static long factorial(long x) {
        long total = 1;
        for (int i = 2; i <= x; i++)
            total = (total * i) % M;
        return total;
    }

    static long power(long x, long n) {
        if (n == 0) {
            return 1;
        }
        long pow = power(x, n / 2L);
        if ((n & 1) == 1) {
            return (x * (pow) * (pow));
        }
        return (pow * pow);
    }
    private static <T> String ts(T t) {
        if(t==null) {
            return "null";
        }
        try {
            return ts((Iterable) t);
        }catch(ClassCastException e) {
            if(t instanceof int[]) {
                String s = Arrays.toString((int[]) t);
                return "{"+s.substring(1, s.length()-1)+"}";
            }else if(t instanceof long[]) {
                String s = Arrays.toString((long[]) t);
                return "{"+s.substring(1, s.length()-1)+"}";
            }else if(t instanceof char[]) {
                String s = Arrays.toString((char[]) t);
                return "{"+s.substring(1, s.length()-1)+"}";
            }else if(t instanceof double[]) {
                String s = Arrays.toString((double[]) t);
                return "{"+s.substring(1, s.length()-1)+"}";
            }else if(t instanceof boolean[]) {
                String s = Arrays.toString((boolean[]) t);
                return "{"+s.substring(1, s.length()-1)+"}";
            }
            try {
                return ts((Object[]) t);
            }catch(ClassCastException e1) {
                return t.toString();
            }
        }
    }
    private static <T> String ts(T[] arr) {
        StringBuilder ret = new StringBuilder();
        ret.append("{");
        boolean first = true;
        for(T t: arr) {
            if(!first) {
                ret.append(", ");
            }
            first = false;
            ret.append(ts(t));
        }
        ret.append("}");
        return ret.toString();
    }
    private static <T> String ts(Iterable<T> iter) {
        StringBuilder ret = new StringBuilder();
        ret.append("{");
        boolean first = true;
        for(T t: iter) {
            if(!first) {
                ret.append(", ");
            }
            first = false;
            ret.append(ts(t));
        }
        ret.append("}");
        return ret.toString();
    }
    public static void dbg(Object... o) {
        if(LOCAL) {
            System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [");
            for(int i = 0; i<o.length; i++) {
                if(i!=0) {
                    System.err.print(", ");
                }
                System.err.print(ts(o[i]));
            }
            System.err.println("]");
        }
    }

}