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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;










public class Main {
	public static int MAX_SIZE = 1000001 ; 
	public static Vector<Boolean> isprime = new Vector<Boolean>(MAX_SIZE); 
	public static Vector<Integer> primes = new Vector<Integer>(MAX_SIZE) ;
	public static Vector<Integer> SPF = new Vector<Integer>(MAX_SIZE);
	
	
	
	public static void sieve (int n ) {
		isprime.set(0,false); 
		isprime.set(1, false) ; 
		for (int i  = 2 ; i < n ;  i ++ )  {
			if (isprime.get(i)) {
				primes.add(i);
				SPF.add(i);
			}
			for (int j = 2 ; i*primes.get(j) <= n  ; j +=i ) {
				
			}
			
		}
		
	}
	
	
	public static ArrayList<Stack<Integer>> as = new ArrayList<Stack<Integer>>();
	
	
	public static int k ;
	public static Stack<Integer>q=new Stack<Integer>();
	
	public static void  permutation (int [] a,int n , int mask, int taken) {
		
		if (taken == n  ) {

			arr = q.toArray();
			backtrack((int)arr[0],0, 1);
			return ;
			
			
		}
		else {
			for(int i = 0 ; i < n ; i++  ) {
				if ((mask &(1 << i)) == 0 ) {
					q.add((int)a[i]);

					
					permutation(a,n, mask | (1 <<i) , taken+1);
					q.pop();
				}
			}
		}
		
	}
	
	
	
	
	
	
	
 
	public static boolean gsd(long x , int y) {
		for(int i = 2 ; i <= Math.min(y, x) ; i ++ ) {
			if (x%i == 0 && y%i == 0 ) return true;
		}
		return false;
	}
	public static int s(long x) {
		int sum = 0 ; 
		do {
			sum += x%10 ; 
			x /= 10;
		}while(x >0 );
		return sum;
	}
	public static int right(String s) {
		int c = 0 ; 
		for(int i = s.length()-1 ; i>=0; i -- ) {
			if(s.charAt(i) == 'a') c++ ; 
			else break;
		}
		return c; 
	}
	public static int left(String s) {
		int c = 0 ; 
		for(int i = 0 ; i<s.length(); i ++ ) {
			if(s.charAt(i) == 'a') c++ ; 
			else break;
		}
		return c; 
	}
	public static boolean onlyas (String s) {
		for (int i = 0 ; i < s.length() ; i ++ ) {
			if (s.charAt(i) != 'a') return false ; 
		}return true;
	}
	public static String convert(String s) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0 ; i < s.length() ; i ++ ) {
			if (s.charAt(i) == '1') sb.append("0"); 
			else sb.append("1");
		}
		return sb.toString();
	}
	public static int check (String s) {
//		boolean flag = false ; 
		for (int i = 0 ; i < s.length() ; i ++) {
			if (Character.isDigit(s.charAt(i)) ) {
				for (int j = i ; j <s.length() ; j ++ ) {
					if (!Character.isDigit(s.charAt(j)))return 0 ; 
				}
				return 1 ;
			}
				
		}
		return 1;
	}
	public static String s26 (int n) {
		StringBuilder st = new StringBuilder();
		while (n >0) {
			int x = n%26 ; 
			n /= 26 ;
			if (x-1 <0 ) {
				x = 26;n-- ;
			}
			st.insert(0, letters[x-1]);
		}
		return st.toString();
	}
	
	public static int sum = 0 ;
	public static int tokens = 0 ; 
	public static Object arr [] = new Integer [5];
	public static boolean flag = false ; 
	public static void backtrack (int ss , int idx , int tks) {
		
		if (tks == 5 )  {
//			System.out.println(ss + " ");
			if (ss  == 23 ) {//System.out.print(ss+" " );
				flag = true ; return ;
			}
		}else {
			 backtrack(ss+ (int)arr[idx+1], idx+1, tks+1);
			 backtrack(ss*(int)arr[idx+1], idx+1, tks+1);
			 backtrack(ss-(int)arr[idx+1], idx+1, tks+1);
			
		}
	
	}
	public static int length (int n) {
		int l = 0 ;
		while (n > 0 ) {
			l ++ ; 
			n /=10 ; 
		}
		return l ; 
	}
	public static int GSD (int x , int y  )  {
		for (int i = x ; i >0 ; i -- ) {
			if (x% i== 0 && y % i==  0 ) return i;
		}
		return 1 ; 
	}
	
	public static char [] letters = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'
			,'P','Q','R','S','T','U','V','W','X','Y', 'Z'};
	public static void main(String[] args)  throws IOException, InterruptedException{
		PrintWriter pw = new PrintWriter(System.out);
		Scanner sc = new Scanner (System.in);

	int t = sc.nextInt();
	while (t-- >  0 ) {
		int n = sc.nextInt();
		int c = 0 ; 
		int y = 0 ; 
		for (int x = 3 ; x <= Math.sqrt(2*n) ; x+=2 ) {
			y = (x*x) -1 ; y/=2;
			if (y+1 <=n )  c++ ; 
				
			
			
		}
		
		pw.println(c);
	}
		pw.close ();
	}
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
	}
 
 
}

/*
while (true) {
		
		
		int []a = new int [5];
	
		for (int i = 0 ; i < 5 ; i ++ ) {
			arr[i]= sc.nextInt(); 
			a[i]= (int)arr[i];; 
		}
		if (a[0] == 0) break ;
		permutation(a, 5, 0, 0);
	
		pw.println(flag ? "Possible":"Impossible");
		}

			
*/