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.lang.reflect.Type;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.LockSupport;

public class Main {

    static class Task {

        public static String roundS(double result, int scale) {
            String fmt = String.format("%%.%df", scale);
            return String.format(fmt, result);
//        DecimalFormat df = new DecimalFormat("0.000000");
//        double result = Double.parseDouble(df.format(result));
        }

        int rt(int x) {
            if (x != fa[x]) {
                int to = rt(fa[x]);
                dp[x] ^= dp[fa[x]];
                fa[x] = to;
                return to;
            }
            return x;
        }

        void combine(int x, int y, int val) {
            int rt1 = rt(x);
            int rt2 = rt(y);

            if (rt1 == rt2) return;

            fa[rt1] = rt2;
            dp[rt1] = dp[x] ^ dp[y] ^ val;
            g--;

        }


        int fa[], dp[];
        int g;


        static int MAXN = 10000;
        static Random rd = new Random(348957438574659L);

        static int[] ch[],val,size,rnd,cnt;
        static int len=0,rt=0;

        // return new node, the node below s
        static int rotate(int s,int d){
            // child
            int x=ch[s][d^1];
            // give me grandson
            ch[s][d^1] = ch[x][d];
            // child become father
            ch[x][d]=s;
            // update size, update new son first
            update(s);
            update(x);
            return x;
        }

        static void update(int s){
            size[s] = size[ch[s][0]] + size[ch[s][1]] + cnt[s];
        }

        // 0 for left, 1 for right
        static int cmp(int x,int num) {
            if (val[x] == num) return -1;
            return num < val[x] ? 0 : 1;
        }

        static int insert(int s,int num) {
            if(s==0){
                s=++len;
                val[s]=num;size[s]=1;rnd[s]=rd.nextInt();cnt[s] = 1;
            }else{
                int d=cmp(s,num);
                if(d!=-1) {
                    ch[s][d]=insert(ch[s][d],num);
                    // father's random should be greater
                    if(rnd[s]<rnd[ch[s][d]]) {
                        s=rotate(s,d^1);
                    }else {
                        update(s);
                    }
                }else{
                    ++cnt[s];++size[s];
                }
            }
            return s;
        }

        static int del(int s,int num) {
            int d = cmp(s, num);
            if (d != -1) {
                ch[s][d] = del(ch[s][d], num);
                update(s);
            }else if (ch[s][0] * ch[s][1] == 0) {
                if(--cnt[s]==0){
                    s = ch[s][0] + ch[s][1];
                }
            } else {
                int k = rnd[ch[s][0]] < rnd[ch[s][1]] ? 0 : 1;
                // k points to smaller random value,then bigger one up
                s = rotate(s, k);
                // now the node with value num become the child
                ch[s][k] = del(ch[s][k], num);
                update(s);
            }
            return s;
        }

        static int getKth(int s, int k){
            int lz = size[ch[s][0]];
            if(k>=lz+1&&k<=lz+cnt[s]){
                return val[s];
            }else if(k<=lz){
                return getKth(ch[s][0], k);
            }else{
                return getKth(ch[s][1], k-lz-cnt[s]);
            }
        }
        // value可能不在树中出现，定义为比自己小的数的个数+1
        static int getRank(int s,int value){
            if(s==0)return 1;
            if(value==val[s])return size[ch[s][0]] + 1;
            if(value<val[s])return getRank(ch[s][0],value);
            return getRank(ch[s][1],value)+size[ch[s][0]] + cnt[s];
        }


        static int getPre(int data){
            int ans= -1;
            int p=rt;
            while(p>0){
                if(data>val[p]){
                    if(ans==-1 || val[p]>val[ans])
                        ans=p;
                    p=ch[p][1];
                }
                else p=ch[p][0];
            }
            return ans!=-1?val[ans]:(-2147483647);
        }

        static int getNext(int data){
            int ans= -1;
            int p=rt;
            while(p>0){
                if(data<val[p]){
                    if(ans==-1 || val[p]<val[ans])
                        ans=p;
                    p=ch[p][0];
                }
                else p=ch[p][1];
            }

            return ans!=-1?val[ans]:2147483647;
        }


        static boolean find(int s,int num){
            while(s!=0){
                int d=cmp(s,num);
                if(d==-1) return true;
                else s=ch[s][d];
            }
            return false;
        }
        static int ans = -10000000;
        static boolean findX(int s,int num){
            while(s!=0){
                if(val[s]<=num){
                    ans = num;
                }
                int d=cmp(s,num);
                if(d==-1) return true;
                else {
                    s = ch[s][d];
                }
            }
            return false;
        }

        long gcd(long a,long b){
            if(b==0) return a;
            return gcd(b,a%b);
        }


        public void solve(int testNumber, InputReader in, PrintWriter out) {


            int t = in.nextInt();
//
//
            outer:for(int j=0;j<t;++j){
               int n = in.nextInt();
               int v = (int)Math.sqrt(2*n-1);
                int ans = (v+1)/2-1;
                out.println(ans);












            }






//            while(true) {
//                int n = in.nextInt();
//
//                int m  =in.nextInt();
//
//                fa = new int[n];
//                dp = new int[n];
//                for(int i=0;i<n;++i){
//                    fa[i] = i;
//                }
//                g =  n;
//                int c = 0;
//                int as[] = new int[n];
//                int bs[] = new int[n];
//                char xs[] = new char[n];
//
//                int at = -1;
//                Set<Integer> st = new HashSet<>();
//
//                for (int i = 0; i < n; ++i) {
//                    String line = in.next();
//                    int p = 0;
//                    int a = 0;
//                    while(Character.isDigit(line.charAt(p))){
//                        a =  a*10 + (line.charAt(p)-'0'); p++;
//                    }
//                    char x = line.charAt(p++);
//
//                    int b = 0;
//                    while(p<line.length()){
//                        b =  b*10 + (line.charAt(p)-'0'); p++;
//                    }
//
//                    as[i] = a;
//                    xs[i] = x;
//                    bs[i] = b;
//
//                    if(x=='='){
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]!=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, 0);
//                        }
//                    }else if(x=='<'){
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]>=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, -1);
//                        }
//                    }else{
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]<=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, 1);
//                        }
//                    }
//
//
//                }
//                if(g==1||c>=2){
//                    out.println("Impossible");
//                    continue;
//                }
//
//
//                for(int xuan: st){
//
//
//
//
//                }
//
//
//
//
//
//
//            }






        }


        static long mul(long a, long b, long p)
        {
            long res=0,base=a;
            while(b>0)
            {
                if((b&1L)>0)
                    res=(res+base)%p;
                base=(base+base)%p;
                b>>=1;
            }
            return res;
        }

        static long mod_pow(long k,long n,long p){
            long res = 1L;
            long temp = k%p;
            while(n!=0L){
                if((n&1L)==1L){
                    res = mul(res,temp,p);
                }
                temp = mul(temp,temp,p);
                n = n>>1L;
            }
            return res%p;
        }


        public static double roundD(double result, int scale){
            BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
            return bg.doubleValue();
        }



    }
    private static void solve() {
        InputStream inputStream = System.in;
        //InputStream inputStream  = new FileInputStream(new File("D:\\chrome_download\\travel1.in"));
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task task = new Task();
        task.solve(1, in, out);
        out.close();
    }
    public static void main(String[] args) {
       // new Thread(null, () -> solve(), "1", (1 << 10 ) ).start();
        solve();
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String nextLine() {
            String line = null;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public char nextChar() {
            return next().charAt(0);
        }
        public int[] nextArray(int n) {
            int res[] = new int[n];
            for (int i = 0; i < n; ++i) {
                res[i] = nextInt();
            }
            return res;
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}