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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;


public class Edu104 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<Integer>q,w,primes;
	static ArrayList<Integer>adj[];
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>h,tmp;
	static boolean[]v;
	static int[]a,b,c,d;
	static int dp[][][];
	static int A,B,n,m,k,mt[][];
	static int oo=Integer.MIN_VALUE;
	static String s,tt;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		//A();
    	//B();
		//primes=new ArrayList<Integer>();
		//primesH=new HashSet<Integer>();
	//	sieveOfEratosthenes(50);
		//C();
		D();
		//E();
		//minimum for subarrays of fixed length
		//F();
		out.close();
	}
	  private static void A() throws IOException {
		  int t=ni();
			while(t-->0) {
				int n=sc.nextInt();
				int[][]aa=new int[n][2];
				a=new int[n];
				for(int i=0;i<n;i++) {
					aa[i][0]=ni();
					a[i]=aa[i][0];
					aa[i][1]=i;
				}
				Arrays.sort(aa,(u,v)->u[0]-v[0]);
				Arrays.sort(a);
				int cn=0;
				for(int i=1;i<n;i++) {
					if(a[i]>a[0])cn++;
				}
				out.println(cn);
			}
		
	   }
		static void B() throws IOException {
			int t=ni();
			while(t-->0) {
				int n=ni(),k=ni();
				int[]pt=new int[2*n-2];
				boolean dec=true;
				for(int i=0,cnt=n;i<pt.length;i++) {
					pt[i]=cnt;
					if(dec) {
						cnt--;
						if(cnt==1) {
							dec=false;
						}
					}else {
						cnt++;
					}
				}
				//disp(pt);
				if(n%2==0)//no overlap
				{
					out.println(k%n==0?n:k%n);
				}else {
						int[]pt2=new int[2*n-2];
						dec=false;
						for(int i=0,cnt=1;i<pt2.length;i++) {
							if(cnt==pt[i]) {
								cnt++;
							}
							pt2[i]=cnt;
							
							
								
								if(cnt==n) {
									cnt=0;
								}
								cnt++;
							
						}
						//disp(pt2);
						out.println(pt2[(k-1)%(2*n-2)]);
				
				}
						
			}
		}
		static void B2() throws IOException {
			 int t=ni();
			  while(t-->0) {
				 
				  
				  
			  }
		}
	  static void C() throws IOException {
		  int t=ni();
		  while(t-->0) {
			 int n=ni(),k=ni();
			 if(n%2==0) {
				 out.println(k%n==0?n:k%n);
			 }
			 else {
				 
			 }
			  
		  }
		  
		}



	static void D() throws IOException {
		int t=ni();
		while(t-->0) {
			int n=sc.nextInt();
			long ans=0;
			for(int i=0;;i++) {
				long cur=2*(i+1)*(i+2)*1l;
				if(cur>=n)break;
				ans++;
			}
			out.println(ans);
		}
		
		
	}
	private static int sum(char[] ss) {
		int sum=0;
		for(int i=0;i<ss.length;i++) {
			sum+=(ss[i]-'0');
		}
		return sum;
	}
	static int gcd (int a, int b) {
	    return b==0?a:gcd (b, a % b);
	}
	static int lcm (int a, int b) {
	    return a / gcd(a, b) * b;
	}
	static void E() throws IOException {
		int t=ni();
		while(t-->0) {
			
			
		}
		
		
		
	}
	static final Random random=new Random();
	static void ruffleSort(int[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	static void F() throws IOException{
		int t=1;
		while(t-->0) {
			
		}
		
	}


	
	static void G() throws IOException{
		int t=1;
		while(t-->0) {

			
			
			
		}
		
	}
	private static void disp(int[] revl) {
		for(int i=0;i<revl.length;i++) {
			out.print(revl[i]+" ");
		}
		out.println();
	}

	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}