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:
//package com.company;


import java.math.*;
import java.util.*;
import java.lang.*;
import java.io.*;
//import javafx.util;



public final class Main {

    public static long xy(long n,long k  )
    {

        if(n%2 == 0)
        {
            if(n>=k)
               return  k;// System.out.println(k);
            else
            {
                long g = k/n;
                long h = k%n;
                if(h == 0)
                {
                   return n;// System.out.println(n);
                }
                else
                {
                  return h; // System.out.println(h);
                }
            }
        }
        else
        {

            long jj = n/2 ;
            if(jj>=k)
            {
               return  k;// System.out.println(k);
            }
            else
            {
                long g = k/jj;

                long h = k%n;
               // w
                if(h == 0)
                {
                   if (g>n)
                   {
                       // System.out.println(n);
                       long v=g%n;
                       if (v==0)
                       {
                           return n;
                       }
                       else return v;
                   }
                   else
                   {
                       return g;
                   }
                }
                else
                {
                    //System.out.println(h);

                    if (h+g<=n)
                    {
                        return h+g;
                    }
                    else {
                        g = g+h-n;
                        if (g>n)
                        {
                            // System.out.println(n);
                            long v=g%n;
                            if (v==0)
                            {
                                return n;
                            }
                            else return v;
                        }
                        else
                        {
                            return g;
                        }
                    }
                }
            }

        }

    }

    public static void main(String[] args) throws java.lang.Exception {
        // your code goes here


        FastReader s = new FastReader();

        //  for taking innput of array of length "len"
        //  for taking innput of array of length "len"
//        int len = s.nextInt();
//        int [] arr = new int[len];
//        String [] strs =  s.nextLine().trim().split("\\s+");
//        for (int i = 0; i < len; i++)
//            arr[i] = Integer.parseInt(strs[i]);

        //  for taking innput of array of length "len"
       int t = s.nextInt();
              while(t-->0)
              {
                  long n = s.nextLong();
                 // long k = s.nextLong();
                  long ans = (long)(((long)(Math.sqrt(2*(n-1)+1))- 1)/2);

//                  long x = 2;
//                  while(x*x +1 <=n)
//                  {
//                      long h = x*x +1;
//                      long a = x*x -1;
//                      long b = 2*x;
//                      if(a*a == h+b)
//                      {
//                          ans++;
//                      }
//                      if(b*b == a+h)
//                      {
//                          ans++;
//                      }
//
//
//                      x++;
//                  }

                  System.out.println(ans);

              }

            //  for printing ar array of size "len"
            //   StringBuffer sb = new StringBuffer();
            //   for (int i = 0; i < len; i++)
            //   sb.append(arr[i] + " ");
            //
            //   System.out.println(sb);




    }









    public static  class Pair<L,R> {
        private L l;
        private R r;
        public Pair(L l, R r){
            this.l = l;
            this.r = r;
        }
        public L getL(){ return l; }
        public R getR(){ return r; }
        public void setL(L l){ this.l = l; }
        public void setR(R r){ this.r = r; }
    }



    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;
        }
    }

}