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.util.*;
import java.io.*;

public class Main {
	static final int M = 1000000007;

	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long[] readArrayLong(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		int[] readArrayInt(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		long nextLong() {
			return Long.parseLong(next());
		}
	}

	// sorting template
	static void sortLong(long[] a) {
		ArrayList<Long> l = new ArrayList<>();
		for (long i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static void sortInt(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static class Graph {
		private ArrayList<Integer> adj[];
		public String s;
		public String dpch;

		Graph(int n) {
			adj = new ArrayList[n + 1];
			for (int i = 1; i <= n; i++) {
				adj[i] = new ArrayList<>();
			}
		}

		void addEdges(int u, int v) {
			adj[u].add(v);
			adj[v].add(u);
		}

		void dfs(int v, boolean[] vis) {
			vis[v] = true;
			for (int u : adj[v]) {
				if (!vis[u]) {
					dfs(u, vis);
				}
			}
		}

		int bfs(int v, boolean[] vis, int[] ans) {
			int sum = 0;
			Queue<Integer> q = new LinkedList<>();
			q.add(v);
			vis[v] = true;
			ans[v] = 0;
			while (q.size() > 0) {
				int node = q.poll();
				for (int u : adj[node]) {
					if (!vis[u]) {
						vis[u] = true;
						ans[u] = ans[node] + 1;
						q.add(u);
					}
				}
			}
			return sum;
		}
	}

	static class Pair<F, S> {
		F first;
		S second;

		Pair(F first, S second) {
			this.first = first;
			this.second = second;
		}

		public F getFirst() {
			return this.first;
		}

		public S getSecond() {
			return this.second;
		}
		// Sort on basis of first term, reverse p1.first and p2.first to sort in desc
		// Collections.sort(a, (p1, p2) -> (p1.first - p2.first));

		// Sort on the basis of second term, reverse p1.second and p2.second to sort
		// in
		// desc
		// Collections.sort(a, (p1, p2) -> (p1.second - p2.second));
	}

	static int __gcd(int a, int b) {
		if (b == 0)
			return a;
		return __gcd(b, a % b);
	}

	public static int subtree, maxNode, maxDist;
	public static int[] dist;
	public static int[] connected;

	public static void main(String[] args) throws IOException {
		FastScanner fs = new FastScanner();
		int t = fs.nextInt();
		StringBuffer res = new StringBuffer();
		for (int tt = 1; tt <= t; tt++) {
			int n = fs.nextInt();
			int count = 0;
			int i = 3;
			while (true) {
				if ((i * i + 1) / 2 > n)
					break;
				else {
					i += 2;
					count++;
				}
			}
			res.append(count).append("\n");		
		}
		System.out.println(res);
	}

	private static int binary_search(int[] a) {
		// initialise left and right in such a way that whole search space is included
		int left = 0;
		int right = a.length;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (condition(mid)) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return left; // left is the minimum K satisfying the given condition as true
	}

	private static boolean condition(int mid) {
		return false;
	}
}