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.math.*;
import java.util.*;
import java.util.stream.*;
import java.text.*;

public class Main {
    private static FastIO sc;

    public static void main(String[] args) {
        sc = new FastIO(System.in, System.out);
        int t = sc.readInt();
        while (t-- > 0) {
            int n = sc.readInt();
            int range = (int) Math.sqrt(2 * n - 1);
            int result = (range - 1) / 2;
            sc.println(result);
        }
        sc.close();
    }

    static void printPrecision(double d) {
        DecimalFormat ft = new DecimalFormat("0.00000000000");//Change the pattern
        sc.println(ft.format(d));
    }

    private static class FastIO {

        public static final int DEFAULT_BUFFER_SIZE = 65536;
        public static final int DEFAULT_INTEGER_SIZE = 11;
        public static final int DEFAULT_LONG_SIZE = 20;
        public static final int DEFAULT_WORD_SIZE = 256;
        public static final int DEFAULT_LINE_SIZE = 8192;
        public static final int EOF = -1;

        private final InputStream in;
        private final OutputStream out;

        private byte[] inBuffer;
        private int nextIn, inLength;
        private byte[] outBuffer;
        private int nextOut;

        private char[] charBuffer;
        private byte[] byteBuffer;

        public FastIO(InputStream in, OutputStream out, int inBufferSize, int outBufferSize) {
            this.in = in;
            this.inBuffer = new byte[inBufferSize];
            this.nextIn = 0;
            this.inLength = 0;

            this.out = out;
            this.outBuffer = new byte[outBufferSize];
            this.nextOut = 0;

            this.charBuffer = new char[DEFAULT_LINE_SIZE];
            this.byteBuffer = new byte[DEFAULT_LONG_SIZE];
        }

        public FastIO(InputStream in, OutputStream out) {
            this(in, out, DEFAULT_BUFFER_SIZE, DEFAULT_BUFFER_SIZE);
        }

        public FastIO(InputStream in, OutputStream out, int bufferSize) {
            this(in, out, bufferSize, bufferSize);
        }

        public char readChar() {
            byte b;
            while (isSpace(b = read()))
                ;

            return (char) b;
        }

        public String readString() {
            byte b;
            while (isSpace(b = read()))
                ;

            int pos = 0;
            do {
                charBuffer[pos++] = (char) b;
                ensureCapacity(pos);
            } while (!isSpace(b = read()));

            return new String(charBuffer, 0, pos);
        }

        public String readLine() {
            byte b;
            int pos = 0;

            while (!isLine(b = read())) {
                charBuffer[pos++] = (char) b;
                ensureCapacity(pos);
            }

            return new String(charBuffer, 0, pos);
        }

        public int readInt() {
            byte b;
            while (isSpace(b = read()))
                ;

            boolean negative = false;
            int result = b - '0';
            if (b == '-') {
                negative = true;
                result = 0;
            }

            while (isDigit(b = read()))
                result = (result * 10) + (b - '0');

            return negative ? -result : result;
        }

        public long readLong() {
            byte b;
            while (isSpace(b = read()))
                ;

            boolean negative = false;
            long result = b - '0';
            if (b == '-') {
                negative = true;
                result = 0;
            }

            while (isDigit(b = read()))
                result = (result * 10) + (b - '0');

            return negative ? -result : result;
        }

        public float nextFloat() {
            byte b;
            while (isSpace(b = read()))
                ;

            int pos = 0;
            do {
                charBuffer[pos++] = (char) b;
            } while (!isSpace(b = read()));

            return Float.parseFloat(new String(charBuffer, 0, pos));
        }

        public float nextFloat2() {
            byte b;
            while (isSpace(b = read()))
                ;

            boolean negative = false;
            float result = b - '0';
            if (b == '-') {
                negative = true;
                result = 0;
            }

            while (isDigit(b = read()))
                result = (result * 10) + (b - '0');

            float d = 1;
            if (b == '.') {
                while (isDigit(b = read()))
                    result += (b - '0') / (d *= 10);
            }

            return negative ? -result : result;
        }

        public double readDouble() {
            byte b;
            while (isSpace(b = read()))
                ;

            int pos = 0;
            do {
                charBuffer[pos++] = (char) b;
            } while (!isSpace(b = read()));

            return Double.parseDouble(new String(charBuffer, 0, pos));
        }

        public double nextDouble2() {
            byte b;
            while (isSpace(b = read()))
                ;

            boolean negative = false;
            double result = b - '0';
            if (b == '-') {
                negative = true;
                result = 0;
            }

            while (isDigit(b = read()))
                result = (result * 10) + (b - '0');

            double d = 1;
            if (b == '.') {
                while (isDigit(b = read()))
                    result += (b - '0') / (d *= 10);
            }

            return negative ? -result : result;
        }

        public BigInteger readBigInteger() {
            return new BigInteger(readString());
        }

        public BigDecimal readBigDecimal() {
            return new BigDecimal(readString());
        }

        public char[] nextToCharArray() {
            byte b;
            while (isSpace(b = read()))
                ;

            int pos = 0;
            do {
                charBuffer[pos++] = (char) b;
                ensureCapacity(pos);
            } while (!isSpace(b = read()));

            char[] array = new char[pos];
            System.arraycopy(charBuffer, 0, array, 0, pos);
            return array;
        }

        public int[] readIntArray(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
                array[i] = readInt();

            return array;
        }

        public long[] readLongArray(int size) {
            long[] array = new long[size];
            for (int i = 0; i < size; i++)
                array[i] = readLong();

            return array;
        }

        public int[][] nextInt2DArray(int Y, int X) {
            int[][] array = new int[Y][X];
            for (int y = 0; y < Y; y++)
                for (int x = 0; x < X; x++)
                    array[y][x] = readInt();

            return array;
        }

        public void print(char c) {
            write((byte) c);
        }

        public void print(char[] chars) {
            print(chars, 0, chars.length);
        }

        public void print(char[] chars, int start) {
            print(chars, start, chars.length);
        }

        public void print(char[] chars, int start, int end) {
            for (int i = start; i < end; i++)
                write((byte) chars[i]);
        }

        public void print(String s) {
            for (int i = 0; i < s.length(); i++)
                write((byte) s.charAt(i));
        }

        public void print(int i) {
            if (i == 0) {
                write((byte) '0');
                return;
            }
            if (i == Integer.MIN_VALUE) {
                write((byte) '-');
                write((byte) '2');
                write((byte) '1');
                write((byte) '4');
                write((byte) '7');
                write((byte) '4');
                write((byte) '8');
                write((byte) '3');
                write((byte) '6');
                write((byte) '4');
                write((byte) '8');
                return;
            }

            if (i < 0) {
                write((byte) '-');
                i = -i;
            }

            int pos = 0;
            while (i > 0) {
                byteBuffer[pos++] = (byte) ((i % 10) + '0');
                i /= 10;
            }

            while (pos-- > 0)
                write(byteBuffer[pos]);
        }

        public void print(long l) {
            if (l == 0) {
                write((byte) '0');
                return;
            }
            if (l == Long.MIN_VALUE) {
                write((byte) '-');
                write((byte) '9');
                write((byte) '2');
                write((byte) '2');
                write((byte) '3');
                write((byte) '3');
                write((byte) '7');
                write((byte) '2');
                write((byte) '0');
                write((byte) '3');
                write((byte) '6');
                write((byte) '8');
                write((byte) '5');
                write((byte) '4');
                write((byte) '7');
                write((byte) '7');
                write((byte) '5');
                write((byte) '8');
                write((byte) '0');
                write((byte) '8');
                return;
            }

            if (l < 0) {
                write((byte) '-');
                l = -l;
            }

            int pos = 0;
            while (l > 0) {
                byteBuffer[pos++] = (byte) ((l % 10) + '0');
                l /= 10;
            }

            while (pos-- > 0)
                write(byteBuffer[pos]);
        }

        public void print(float f) {
            String sf = Float.toString(f);
            for (int i = 0; i < sf.length(); i++)
                write((byte) sf.charAt(i));
        }

        public void print(double d) {
            String sd = Double.toString(d);
            for (int i = 0; i < sd.length(); i++)
                write((byte) sd.charAt(i));
        }

        public void printls(char c) {
            print(c);
            write((byte) ' ');
        }

        public void printls(String s) {
            print(s);
            write((byte) ' ');
        }

        public void printls(int i) {
            print(i);
            write((byte) ' ');
        }

        public void printls(long l) {
            print(l);
            write((byte) ' ');
        }

        public void printls(float f) {
            print(f);
            write((byte) ' ');
        }

        public void printls(double d) {
            print(d);
            write((byte) ' ');
        }

        public void printls() {
            write((byte) ' ');
        }

        public void println(char c) {
            print(c);
            write((byte) '\n');
        }

        public void println(char[] chars) {
            print(chars, 0, chars.length);
            write((byte) '\n');
        }

        public void println(String s) {
            print(s);
            write((byte) '\n');
        }

        public void println(int i) {
            print(i);
            write((byte) '\n');
        }

        public void println(long l) {
            print(l);
            write((byte) '\n');
        }

        public void println(float f) {
            print(f);
            write((byte) '\n');
        }

        public void println(double d) {
            print(d);
            write((byte) '\n');
        }

        public void println() {
            write((byte) '\n');
        }

        public void printf(String format, Object... args) {
            String s = String.format(format, args);
            for (int i = 0; i < s.length(); i++)
                write((byte) s.charAt(i));
        }

        public void fprint(char c) {
            print(c);
            flushBuffer();
        }

        public void fprint(String s) {
            print(s);
            flushBuffer();
        }

        public void fprint(int i) {
            print(i);
            flushBuffer();
        }

        public void fprint(long l) {
            print(l);
            flushBuffer();
        }

        public void fprint(float f) {
            print(f);
            flushBuffer();
        }

        public void fprint(double d) {
            print(d);
            flushBuffer();
        }

        public void fprintf(String format, Object... args) {
            printf(format, args);
            flushBuffer();
        }

        private byte read() {
            if (nextIn >= inLength) {
                if ((inLength = fill()) == EOF)
                    return EOF;
                nextIn = 0;
            }

            return inBuffer[nextIn++];
        }

        private void write(byte b) {
            if (nextOut >= outBuffer.length)
                flushBuffer();

            outBuffer[nextOut++] = b;
        }

        private int fill() {
            try {
                return in.read(inBuffer, 0, inBuffer.length);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        public void flush() {
            flushBuffer();
        }

        private void flushBuffer() {
            if (nextOut == 0)
                return;

            try {
                out.write(outBuffer, 0, nextOut);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }

            nextOut = 0;
        }

        public void close() {
            flush();
        }

        public void exit(char c) {
            fprint(c);
            System.exit(0);
        }

        public void exit(String s) {
            fprint(s);
            System.exit(0);
        }

        public void exit(int i) {
            fprint(i);
            System.exit(0);
        }

        public void exit(long l) {
            fprint(l);
            System.exit(0);
        }

        public void exit(float f) {
            fprint(f);
            System.exit(0);
        }

        public void exit(double d) {
            fprint(d);
            System.exit(0);
        }

        public void exit(String format, Object... args) {
            fprintf(format, args);
            System.exit(0);
        }

        public void exit() {
            flushBuffer();
            System.exit(0);
        }

        private void ensureCapacity(int size) {
            if (size < charBuffer.length)
                return;

            char[] array = new char[size * 2];
            System.arraycopy(charBuffer, 0, array, 0, size);
            charBuffer = array;
        }

        private boolean isDigit(byte b) {
            return b >= '0' && b <= '9';
        }

        private boolean isLine(byte b) {
            return b == '\n' || b == '\r' || b == EOF;
        }

        private boolean isSpace(byte b) {
            return b == ' ' || b == '\t' || b == '\n' || b == '\r' || b == '\f' || b == EOF;
        }
    }
}