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 \le a \le b \le c \le 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 \le t \le 10^4$) — the number of test cases.

Each test case consists of one line containing one integer $n$ ($1 \le n \le 10^9$).


-----Output-----

For each test case, print one integer — the number of triples of integers $(a, b, c)$ with $1 \le a \le b \le c \le n$ such that they are Pythagorean according both to the real definition and to the formula Vasya came up with.


-----Examples-----

Input
3
3
6
9
Output
0
1
1


-----Note-----

The only Pythagorean triple satisfying $c = a^2 - b$ with $1 \le a \le b \le c \le 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$.

Difficulty: MEDIUM
Tags: Number theory

Sorting

Mathematics

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
import math
for tt in range(int(input())):
	n = int(input())
	ans = 0
	x = (-1 + int(math.sqrt(-1 + 2 * n))) // 2
	print(x)


import sys
input = sys.stdin.readline
from bisect import bisect
for _ in range(int(input())):
	n = int(input())
	x = int((2 * n - 1) ** 0.5)
	print((x - 1) // 2)


import os, sys
from io import BytesIO, IOBase

def some_random_function():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def main():
	from bisect import bisect_right
	i = 5
	x = [5]
	while x[-1] <= 10 ** 9:
		x.append(i * i // 2 + 1)
		i += 2
	x.pop()
	for _ in range(int(input())):
		n = int(input())
		print(bisect_right(x, n))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def some_random_function1():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function2():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function3():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function4():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
main()


import math
num = int(input())
questions = []
for i in range(num):
	questions.append(int(input()))
for n in questions:
	top = math.floor(math.sqrt(2 * n - 1))
	ans = (top - 3) // 2 + 1
	print(ans)


k = int(input())
s = str()
for i in range(k):
	n = int(input())
	if n < 5:
		s = s + '0' + '\n'
	else:
		a = int((2 * n - 1) ** (1 / 2))
		if a % 2 == 0:
			a = a - 1
			a = int(a / 2)
		elif a % 2 != 0:
			a = int(a / 2)
		s = s + str(a) + '\n'
print(s)


def solve():
	n = int(input())
	(l, r) = (0, int(1000000000.0))
	while r - l > 1:
		m = (r + l) // 2
		if m * m <= (n - 1) * 2 + 1:
			l = m
		else:
			r = m
	print((l - 1) // 2)
	return
	ans = 0
	for a in range(3, 64000, 2):
		qa = a * a
		if qa & 1 == 0:
			continue
		b = (qa - 1) // 2
		c = b + 1
		if c > n:
			break
		if c * c == b * b + qa:
			ans += 1
	print(ans)
t = int(input())
while t > 0:
	t -= 1
	solve()


import sys
input = sys.stdin.readline
import math

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			c += 1
	return c
import math

def CountSquares(a, b):
	return math.floor(math.sqrt(b)) - math.ceil(math.sqrt(a)) + 1
for _ in range(int(input())):
	x = int(input())
	d = math.sqrt(2 * x - 1)
	e = (d + 1) // 2
	print(int(e) - 1)


from math import sqrt
import operator
import sys
inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split(' ')]
	return res

def read_str():
	return input().rstrip()

def check_seq(n, c_max_l, results_l):
	if n < c_max_l[0]:
		return 0
	l = 0
	r = len(c_max_l) - 1
	while l <= r:
		mid = (l + r) // 2
		if c_max_l[mid] <= n:
			res = mid
			l = mid + 1
		else:
			r = mid - 1
	return results_l[res]

def get_results():
	results_l = []
	c_max_l = []
	c_max = 1000000000
	cur_c = 0
	a = 1
	while True:
		b = a * a - 1
		if b % 2 == 0:
			b = b // 2
		else:
			b = -1
		if b != -1 and b > 0:
			cur_c = a * a - b
			c_max_l.append(cur_c)
			if not results_l:
				results_l.append(1)
			else:
				results_l.append(results_l[-1] + 1)
		a += 1
		if cur_c > c_max:
			break
	return (c_max_l, results_l)

def main():
	cnt = read_one_int()
	(c_max_l, results_l) = get_results()
	for _ in range(cnt):
		n = read_one_int()
		res = check_seq(n, c_max_l, results_l)
		print(res)
main()


import math
from collections import OrderedDict, defaultdict
i = 2
x = int(9999999999 ** 0.5) + 100
ans = 0
a = 0
b = 0
c = 0
d = defaultdict(lambda : 0)
dr = OrderedDict()

def binarySearch(arr, l, r, x):
	le = r
	while l < r:
		mid = (l + r) // 2
		if x == arr[mid][0]:
			return arr[mid][1]
		elif x > arr[mid][0]:
			l = mid + 1
		else:
			r = mid - 1
	i = max(0, mid - 10)
	ans = 0
	for i in range(i, le + 1):
		if arr[i][0] > x:
			return ans
		elif arr[i][0] == x:
			return arr[i][1]
		else:
			ans = arr[i][1]
while i <= x:
	a = i
	b = (a * a - 1) // 2
	c = b + 1
	if a * a + b * b == c * c:
		ans += 1
		if d[a, b, c] != 0:
			ans -= 1
		else:
			d[a, b, c] = ans
			dr[c] = ans
	i += 1
l = [[x, y] for (x, y) in dr.items()]
y = len(l)
for _ in range(int(input())):
	n = int(input())
	ans = 0
	ans = binarySearch(l, 0, y - 1, n)
	print(ans)


from math import sqrt

def main():
	for _ in range(int(input())):
		n = int(sqrt(2.0 * float(input()) - 1.0))
		n -= 1 - n % 2
		print(n // 2)
main()


for _ in range(int(input())):
	n = int(input())
	ans = (n * 2 - 1) ** (1 / 2) - 1
	ans = ans // 2
	print(int(ans))


import math

def rootexp(n):
	return math.floor((-1 + math.floor(math.sqrt(2 * n - 1))) / 2)

def answer(n):
	return rootexp(n)
list = []
k = int(input())
for i in range(0, k):
	n = int(input())
	list.append(n)
answers = []
for i in range(0, k):
	answers.append(answer(list[i]))
for i in range(0, k):
	print(answers[i])


for _ in range(int(input())):
	n = int(input())
	i = 3
	ans = 0
	while (i ** 2 - 1) // 2 < n:
		ans += 1
		i += 2
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = math.floor(math.sqrt(2 * n - 1))
	print((a + 1) // 2 - 1)


for _ in range(int(input())):
	n = int(input())
	limit = pow(2 * n - 1, 1 / 2)
	ans = (limit - 1) // 2
	print(int(ans))


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(nmbr()):
	n = nmbr()
	p = 3
	ans = 0
	while 1:
		sq = p * p
		if (sq + 1) // 2 > n:
			break
		ans += 1
		p += 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	k = int((2 * n - 1) ** 0.5)
	if k % 2 == 1:
		print(k // 2)
	else:
		print(k // 2 - 1)


import math
for _ in range(int(input())):
	print(int(int(math.sqrt(2 * int(input()) - 1) - 1) // 2))


for _ in range(int(input())):
	n = int(input())
	ans = 0
	temp = int(pow(2 * n - 1, 0.5))
	if temp % 2 == 0:
		ans = temp // 2 - 1
	else:
		ans = temp // 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	for i in range(3, int((2 * n - 1) ** 0.5) + 1, 2):
		if (i ** 2 - 1) % 2 == 0:
			ans += 1
	print(ans)


t = int(input())
while t:
	t -= 1
	b = int(input())
	if b < 4:
		print(0)
		continue
	b -= 1
	res = int((2 * b + 1) ** 0.5)
	if res % 2 == 0:
		res -= 1
	res = (res - 3) // 2 + 1
	print(res)


import os
import sys
from io import BytesIO, IOBase
import math

def func(n):
	upper = int(math.floor(math.sqrt(2 * n - 1)))
	if upper % 2 == 0:
		upper -= 1
	return (upper - 3) // 2 + 1

def main():
	num_test = int(parse_input())
	for _ in range(num_test):
		n = int(parse_input())
		print(func(n))
parse_input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	x = int((2 * n - 1) ** 0.5)
	print(max(0, (x - 1) // 2))


import io, os, math
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	i = 3
	while (i * i + 1) // 2 <= n:
		ans += 1
		i += 2
	print(ans)


def answer(n):
	l = int((2 * n - 1) ** 0.5)
	c = 0
	for i in range(3, l + 1, 2):
		c += 1
	print(c)
t = int(input())
for i in range(t):
	n = int(input())
	answer(n)


import math
for p in range(int(input())):
	n = int(input())
	print(int((math.sqrt(2 * n - 1) - 1) // 2))


import math
for _ in range(0, int(input())):
	n = int(input())
	t = 2 * n - 1
	t = int(t ** 0.5)
	print(math.ceil(t / 2) - 1)


import math
for _ in range(int(input())):
	n = int(input())
	if n <= 3:
		ans = 0
	else:
		x = math.floor(math.sqrt(2 * n - 1))
		if x % 2 == 0:
			ans = x // 2 - 1
		else:
			ans = x // 2
	print(ans)


import math

def mult_inp():
	return map(int, input().split(' '))

def inp():
	return list(map(int, input().split(' ')))

def binn(dp, it):
	left = 0
	right = len(dp)
	if it < 5:
		return 0
	while 1:
		mid = (left + right) // 2
		if dp[mid] < it and mid + 1 < len(dp) and (dp[mid + 1] < it):
			left = mid
		else:
			return mid
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0.5 * (2 * n - 1) ** 0.5 - 0.5
	print(int(ans))


def arrIn():
	return list(map(int, input().split()))

def mapIn():
	return map(int, input().split())
for ii in range(int(input())):
	n = int(input())
	c = n
	a = c + c - 1
	a = int(a ** 0.5)
	if a % 2 == 0:
		a -= 1
	c = (a - 3) // 2 + 1
	print(c)


from bisect import bisect_left, bisect_right
a = 3
b = 4
c = 5
arr = [5]
while c < 1000000002:
	a += 2
	b = (a ** 2 - 1) // 2
	c = b + 1
	arr.append(c)
t = int(input())
while t:
	n = int(input())
	val = bisect_right(arr, n)
	print(val)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	ans = 0
	i = 3
	while i ** 2 <= 2 * n - 1:
		ans += 1
		i += 2
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	real_n = 2 * n - 1
	i = 3
	count = 0
	while i * i <= real_n:
		count += 1
		i += 2
	print(count)


import math

def koliko(n):
	if n < 5:
		print('0')
		return
	koren = int(math.sqrt(2 * n - 1))
	if koren % 2 == 0:
		t = koren // 2 - 1
	else:
		t = koren // 2
	print(t)
	return
prim = int(input())
while prim > 0:
	n = int(input())
	koliko(n)
	prim -= 1


import math
t = int(input())
ans = []
for i in range(t):
	n = int(input())
	p = int(math.sqrt(2 * n - 1))
	if p % 2 == 0:
		p -= 1
	ans.append(p // 2)
for i in ans:
	print(i)


t = int(input())

def abc(d):
	i = 1
	j = 10 ** 5
	ans = 1
	while i <= j:
		mid = i + (j - i) // 2
		if mid * mid <= d:
			ans = mid
			i = mid + 1
		else:
			j = mid - 1
	return ans
for _ in range(t):
	n = int(input())
	x = 2 * n - 1
	x = abc(x)
	print((x - 1) // 2)


import math
for i in range(int(input())):
	n = int(input())
	if n < 3:
		print(0)
	else:
		c = 0
		a = int(math.sqrt(2 * n - 1))
		print((a - 1) // 2)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	for _ in range(ii()):
		n = ii()
		n *= 2
		ans = 0
		for i in range(1, int(sqrt(n)) + 1):
			x = i * i - 1
			if x > 0 and x % 2 == 0:
				ans += 1
		print(ans)
if file:
	if path.exists('tmp/input.txt'):
		sys.stdin = open('tmp/input.txt', 'r')
		sys.stdout = open('tmp/output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	count = -1
	k = 1
	i = 1
	z = int(math.sqrt((n - 1) / 2 + 0.25) - 0.5)
	print(z)


import math
for _ in range(int(input())):
	n = int(input())
	a = math.sqrt(2 * n - 1)
	if a % 2 == 1:
		print(int(a) // 2)
	else:
		a = int(a)
		if a % 2 == 0:
			a = a - 1
		print(a // 2)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	D = (math.sqrt(4 + 8 * (n - 1)) - 2) / 4
	print(math.floor(D))


import io
import os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
cs = []
a = 3
while True:
	c = (a ** 2 + 1) // 2
	b = c - 1
	if c > 10 ** 9:
		break
	if a ** 2 + b ** 2 == c ** 2:
		cs.append(c)
	a += 2

def solve():
	n = int(input())
	print(bisect.bisect(cs, n))
t = int(input())
for _ in range(t):
	solve()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(200001)]
pp = [0] * 200001

def SieveOfEratosthenes(n=200000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
for _ in range(int(input())):
	n = int(input())
	res = 0
	l = 1
	r = (n - 1) // 2
	while l <= r:
		mid = (l + r) // 2
		a = 2 * mid + 1
		c = (a * a + 1) // 2
		if c <= n:
			res = mid
			l = mid + 1
		else:
			r = mid - 1
	print(res)


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(int(sqrt(2 * n + 1)), 1, -1):
		if i * i < 2 * n and i * i % 2 != 0:
			ans += 1
	print(ans)


for i in range(int(input())):
	print((int((2 * int(input()) - 1) ** 0.5) - 1) // 2)


import math
t = int(input())
while t > 0:
	n = int(input())
	print(int(int(math.sqrt(2 * n - 1) + 1) / 2) - 1)
	t -= 1


maxn = int(400000.0)
c = []
for a in range(3, maxn, 2):
	c.append((a * a + 1) // 2)
for _ in range(int(input())):
	n = int(input())
	(lo, hi, ans) = (0, len(c), 0)
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if c[mid] <= n:
			ans = mid
			lo = mid + 1
		else:
			hi = mid - 1
	ans = 0 if n < 5 else ans + 1
	print(ans)


import math
T = int(input())
for t in range(T):
	N = int(input())
	a = math.sqrt(2 * N - 1)
	print(int((a - 1) // 2))


ans = []
p = []
for i in range(3, 100000, 2):
	p.append(i * i // 2 + 1)
for _ in range(int(input())):
	n = int(input())
	if p[0] > n:
		ans.append(0)
		continue
	L = 0
	R = len(p)
	while R - L > 1:
		M = (L + R) // 2
		if p[M] > n:
			R = M
		else:
			L = M
	ans.append(L + 1)
print('\n'.join(map(str, ans)))


N = int(input())
for t in range(N):
	n = int(input())
	if n < 5:
		print(0)
	else:
		print((int((2 * n - 1) ** 0.5) - 1) // 2)


import math
t = int(input())
for test in range(t):
	n = int(input())
	if n <= 4:
		print(0)
	else:
		d = math.isqrt(2 * n - 1)
		print((d - 1) // 2)


import math
t = int(input())
for j in range(t):
	n = int(input())
	if n <= 3:
		print(0)
	else:
		hh = math.floor(math.sqrt(2 * n - 1))
		if hh % 2 == 0:
			print(hh // 2 - 1)
		else:
			print(hh // 2)


import math

def maths(n):
	t = math.ceil((-3 + (9 - 4 * (2 - n / 2)) ** 0.5) / 2)
	return t

def main():
	arr = []
	length = int(input())
	for i in range(0, length):
		x = int(input())
		arr.append(x)
	for (pos, n) in enumerate(arr):
		t = maths(n)
		print(t)
main()


from sys import *
from math import floor, ceil, sqrt
ws = lambda : map(int, stdin.readline().strip().split())
li = lambda : list(map(int, stdin.readline().strip().split()))
mod = 1000000007

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def prod(l):
	ans = 1
	for i in range(len(l)):
		ans = ans * l[i]
	return ans

def sortindex(l, a):
	c = []
	if a == -1:
		rev = True
	else:
		rev = False
	for i in range(len(l)):
		c.append([l[i], i])
	x = sorted(c, reverse=rev)
	print(x)
	c = []
	for i in range(len(l)):
		c.append(x[i][1])
	return c

def calc(n):
	c = sqrt(1 + 4 * n)
	if c == int(c):
		return c
	else:
		return -1
for _ in range(int(input())):
	n = int(input())
	if n < 5:
		print(0)
	else:
		ans = 0
		for i in range(3, n):
			if i & 1:
				if (i * i + 1) / 2 > n:
					break
				else:
					ans += 1
		print(ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007
for _ in range(stdint()):
	n = stdint()
	res = 0
	for i in range(3, n, 2):
		c = (pow(i, 2) - 1) // 2
		if c + 1 > n:
			break
		res += 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	res = (-2 + (4 + 8 * (n - 1)) ** 0.5) / 4
	print(int(res))


try:
	t = int(input())
	while t != 0:
		n = int(input())
		maxi = int((2 * n - 1) ** 0.5)
		print((maxi + 1) // 2 - 1)
		t -= 1
except EOFError as e:
	print('')


def pytho(n):
	i = 3
	cnt = 0
	while i ** 2 <= 2 * n - 1:
		cnt += 1
		i += 2
	return cnt
for i in range(int(input())):
	print(pytho(int(input())))


import math
t = int(input())
for tc in range(t):
	n = int(input())
	x = int(math.sqrt(2 * n - 1))
	result = (x + 1) // 2 - 1
	print(result)


n = int(input())
lst = [int(input()) for i in range(n)]
for el in lst:
	if el >= 13:
		D = 36 + 8 * (el - 5)
		trio_amount = int((-6 + D ** 0.5) / 4) + 1
	elif el >= 5:
		trio_amount = 1
	else:
		trio_amount = 0
	print(trio_amount)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	x = 2 * n
	x = int(pow(x, 0.5))
	print(max(0, (x + 1) // 2 - 1))


t = int(input())
for _ in range(t, 0, -1):
	n = int(input())
	cnt = 0
	for a in range(3, 50000, +2):
		b = (a * a - 1) / 2
		c = b + 1
		if c < n + 1:
			cnt = cnt + 1
		else:
			break
	print(cnt)


from bisect import bisect_left as bl
import sys
pin = sys.stdin.readline
L = [0] * 22362
L[0] = 1
d = 3
i = 1
for a in range(3, 44725, 2):
	L[i] = L[i - 1] + 2 * d + 2
	d += 4
	i += 1
for T in range(int(pin())):
	N = int(pin())
	M = N * 2
	print(bl(L, M) - 1)


import math
for _ in range(int(input())):
	n = int(input())
	if n < 5:
		print(0)
		continue
	print(int((math.floor(math.sqrt(2 * n - 1)) - 1) // 2))


t = int(input())
for i in range(t):
	n = int(input())
	m = int((2 * n - 1) ** (1 / 2))
	k = int((m - 1) / 2)
	print(k)


import sys
import math
import bisect
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	ans = 0
	i = 3
	while i * i <= 2 * n - 1:
		ans += 1
		i += 2
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	sqrt_root = math.floor(math.sqrt(2 * n))
	ans = math.ceil(sqrt_root / 2) - 1
	print(ans)


import sys
from math import sqrt

def debug(*args):
	print(*args, file=sys.stderr)

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_str_split():
	return list(sys.stdin.readline().strip())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def Main():
	t = read_int()
	for _ in range(t):
		n = read_int()
		a = int(sqrt(2 * n - 1))
		print((a - 1) // 2)
Main()


import math
for _ in range(int(input())):
	x = (-6 + math.sqrt(36 - 8 * (5 - int(input())))) / 4
	print(math.floor(x) + 1)


import math as m
t = int(input())
res = []
for _ in range(t):
	n = int(input())
	a = int(m.sqrt((n - 1) / 2))
	if a * (a + 1) <= (n - 1) / 2:
		res.append(a)
	else:
		res.append(a - 1)
for i in res:
	print(i)


for t in range(int(input())):
	n = int(input())
	l = 3
	r = int((2 * n - 1) ** 0.5)
	ans = 2
	if r % 2 == 0:
		r += 1
	for i in range(r, l - 1, -2):
		if (i ** 2 + 1) // 2 <= n:
			ans = i
			break
	ans = (ans - 3) // 2 + 1
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	for a in range(1, int((2 * n) ** 0.5) + 2, 1):
		k = a ** 2 - 1
		if k % 2 == 0:
			b = k // 2
			c = 1 + b
			if c <= n and c >= b and (b >= a):
				count += 1
	print(count)


from math import floor
for _ in range(int(input())):
	n = int(input())
	print(floor(((2 * n - 1) ** 0.5 - 1) / 2))


import math

def f(n):
	return 2 * n * (n + 1) + 1

def rev(x):
	return math.sqrt(x / 2)
T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	x = rev(n)
	x = int(x)
	if f(x) > n:
		x -= 1
	print(x)


def main():
	num_cases = int(input())
	for case_num in range(1, num_cases + 1):
		solve(case_num)

def solve(case_num):
	n = int(input())
	sol = 0
	for a in range(3, n + 1):
		if a ** 2 > 2 * n - 1:
			break
		if (a ** 2 - 1) % 2 == 0:
			sol += 1
	print(sol)
main()


rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
YN = lambda x: print('YES') if x else print('NO')
mod = lambda x: x % (10 ** 9 + 7)

def d(a):
	d = {}
	for i in a:
		if i not in d:
			d[i] = 0
		d[i] += 1
	return d
for _ in range(rn()):
	n = rn()
	a = 2 * (n - 1) + 1
	a = int(a ** 0.5)
	print(a // 2 + a % 2 - 1)


from math import *
for t in range(int(input())):
	n = int(input())
	a = floor(sqrt(2 * n - 1))
	print(ceil(a / 2) - 1)


t = int(input())
for i in range(t):
	n = int(input())
	print(int(((n * 2 - 1) ** 0.5 - 1) / 2))


import math

def solve(n, ans):
	odd = int(math.ceil(n / 2))
	low = 0
	high = odd
	k = -1
	while low <= high:
		mid = (low + high) // 2
		sq = pow(2 * mid + 1, 2)
		b = sq // 2
		if b + 1 <= n:
			low = mid + 1
			k = mid
		else:
			high = mid - 1
	ans.append(str(k))

def main():
	t = int(input())
	ans = []
	for i in range(t):
		n = int(input())
		solve(n, ans)
	print('\n'.join(ans))
main()


import sys
input = sys.stdin.readline

def solve(arr):
	n = int(input())
	if arr[0][2] > n:
		return 0
	(lo, hi) = (0, len(arr) - 1)
	while lo < hi:
		mid = (lo + hi + 1) // 2
		if arr[mid][2] <= n:
			lo = mid
		else:
			hi = mid - 1
	return lo + 1
arr = []
for a in range(3, 10 ** 5, 2):
	v = pow(a, 2)
	b = (v - 1) // 2
	c = v - b
	if c > 10 ** 9:
		break
	if a + b >= c:
		arr.append((a, b, c))
for _ in range(int(input())):
	print(solve(arr))


T = int(input())
r = 1
while r <= T:
	n = int(input())
	ans = int((2 * n - 1) ** 0.5)
	ans = (ans - 1) // 2
	print(ans)
	r += 1


from math import floor
k = floor((2 * 10 ** 9 - 1) ** 0.5)
dp = [0] * (k + 1)
for a in range(2, k + 1):
	if a % 2 != 0:
		dp[a] = dp[a - 1] + 1
	else:
		dp[a] = dp[a - 1]
for _ in range(int(input())):
	n = int(input())
	x = floor((2 * n - 1) ** 0.5)
	ans = dp[x]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	x = ((2 * n - 1) ** 0.5 - 3) // 2
	print(0 if x < 0 else int(x) + 1)


T = int(input())
ans_ls = [0] * T

def db(*arg):
	print(*arg)
for t in range(T):
	N = int(input())
	ans = 0
	for a in range(1, int((2 * N) ** 0.5) + 10, 2):
		b = a ** 2 // 2
		c = a ** 2 // 2 + 1
		if a <= b and c <= N:
			ans += 1
	ans_ls[t] = ans
for ans in ans_ls:
	print(ans)


for _ in range(int(input())):
	print((int((2 * int(input()) - 1) ** 0.5) - 1) // 2)


n = int(input().strip())
for i in range(n):
	k = int(input().strip())
	print(int((2 * k - 1) ** (1 / 2) - 1) // 2)


from collections import defaultdict, OrderedDict, Counter
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import Queue, PriorityQueue
from heapq import heapify, heappop, heappush
from statistics import median, mean
from math import gcd, sqrt, floor, factorial, ceil, log2, log10, log
import fractions
import copy
from copy import deepcopy
import sys
import io
sys.setrecursionlimit(10 ** 8)
import math
import os
import bisect
import collections
mod = pow(10, 9) + 7
import random
from random import random, randint, randrange
from time import time

def ncr(n, r, p=mod):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def normalncr(n, r):
	r = min(r, n - r)
	count = 1
	for i in range(n - r, n + 1):
		count *= i
	for i in range(1, r + 1):
		count //= i
	return count
inf = float('inf')
adj = defaultdict(set)
visited = defaultdict(int)

def addedge(a, b):
	adj[a].add(b)
	adj[b].add(a)

def bfs(v):
	q = Queue()
	q.put(v)
	visited[v] = 1
	while q.qsize() > 0:
		s = q.get_nowait()
		print(s)
		for i in adj[s]:
			if visited[i] == 0:
				q.put(i)
				visited[i] = 1

def dfs(v, visited):
	if visited[v] == 1:
		return
	visited[v] = 1
	print(v)
	for i in adj[v]:
		dfs(i, visited)

def reverse_bisect_right(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x > a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def reverse_bisect_left(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x >= a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def get_list():
	return list(map(int, input().split()))

def get_str_list_in_int():
	return [int(i) for i in list(input())]

def get_str_list():
	return list(input())

def get_map():
	return map(int, input().split())

def input_int():
	return int(input())

def matrix(a, b):
	return [[0 for i in range(b)] for j in range(a)]

def swap(a, b):
	return (b, a)

def find_gcd(l):
	a = l[0]
	for i in range(len(l)):
		a = gcd(a, l[i])
	return a

def is_prime(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return 0
	return 1

def prime_factors(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return [i] + prime_factors(n // i)
	return [n]
nc = 'NO'
yc = 'YES'
ns = 'No'
ys = 'Yes'

def get_next(a):
	if a == n:
		return 1
	return a + 1

def get_prev(a):
	if a == 1:
		return n
	return a - 1

def div(a, n):
	return a // (n // 2)

def mod(k, n):
	k = k % n
	if k == 0:
		return n
	return k
t = int(input())
for i in range(t):
	n = int(input())
	a = int(sqrt(2 * n - 1))
	if a % 2 == 0:
		a -= 1
	print((a - 1) // 2)


import math
import sys

def main():

	def find(n):
		a = int(math.sqrt(n / 2))
		if a == 0:
			print(a)
		else:
			while 2 * (a ** 2 + a) + 1 > n:
				a -= 1
			while 2 * (a ** 2 + a) + 1 <= n:
				a += 1
			a -= 1
			print(a)
	input = sys.stdin.readline
	i = int(input())
	for _ in range(i):
		n = int(input())
		find(n)
main()


import math
for i in range(int(input())):
	a = int(input())
	print((int(math.sqrt(a + a - 1)) - 1) // 2)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	n = int(inp())
	lo = 1
	hi = n
	x = -1
	while lo <= hi:
		mid = (lo + hi) // 2
		if sqrt((mid + 1) ** 2 - mid ** 2) <= n:
			x = mid
			lo = mid + 1
		else:
			hi = mid - 1
	if x == -1:
		print(0)
		return
	temp = sqrt(2 * x - 1)
	temp = floor(temp)
	print(ceil(temp / 2) - 1)
testcase(int(inp()))


T = int(input())
for x in range(T):
	n = int(input())
	m = int((2 * n - 1) ** 0.5)
	if m % 2 == 0:
		print(int(m / 2 - 1))
	else:
		print(int(m / 2))


import sys
import math
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		c = n
		a = math.sqrt(c * 2 - 1)
		a = math.floor(a)
		ans = (a - 3) // 2 + 1
		print(ans)
main()


import math
T = int(input())
while T:
	T -= 1
	n = int(input()) - 1
	n = (n << 1) + 1
	m = int(math.sqrt(n))
	ans = (m >> 1) - 1
	if m & 1:
		ans += 1
	print(ans)


import sys
input = sys.stdin.readline
from collections import *
from bisect import *
bs = []
for a in range(3, 10 ** 5 + 100):
	if a ** 2 % 2 == 1:
		bs.append((a ** 2 - 1) // 2)
for _ in range(int(input())):
	n = int(input())
	print(bisect_right(bs, n - 1))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	k = int(math.sqrt(2 * n - 1))
	print((k - 1) // 2)


import math
t = int(input())
for i in range(t):
	n = int(input())
	print((int(math.sqrt(2 * n - 1)) - 1) // 2)


from math import *
for i in range(int(input())):
	n = int(input())
	aa = floor(sqrt(2 * n - 1))
	print(ceil(aa / 2) - 1)


import sys
import math

def read_ints():
	return [int(i) for i in sys.stdin.readline().strip().split()]

def read_int():
	return int(sys.stdin.readline().strip())

def pyth(n):
	r = int(math.sqrt(n / 2))
	while 2 * (r + 1) * (r + 1) - 2 * (r + 1) + 1 <= n:
		r += 1
	return r - 1
t = read_int()
for i in range(t):
	n = read_int()
	print(pyth(n))


import sys

def run_case():
	n = int(input())
	print(int((2 * n - 1) ** 0.5 - 1) >> 1)
t = int(input())
for _ in range(t):
	run_case()


t = int(input())
import math
for z in range(t):
	n = int(input())
	m = 2 * n - 1
	s = math.sqrt(m)
	s = math.floor(s) - 1
	print(int(s / 2))


k = int((10 ** 9 * 2 - 1) ** 0.5)
dp = [0] * (k + 1)
for a in range(1, k + 1):
	if a ** 2 % 2 != 0:
		if a ** 2 - 1 > 0:
			dp[a] = dp[a - 1] + 1
		else:
			dp[a] = dp[a - 1]
	else:
		dp[a] = dp[a - 1]
for _ in range(int(input())):
	n = int(input())
	n = int((2 * n - 1) ** 0.5)
	ans = dp[n]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	shit = int((2 * n - 1) ** 0.5)
	if shit % 2 == 0:
		print(shit // 2 - 1)
	else:
		print(shit // 2)


for t in range(int(input())):
	n = int(input())
	print(int(((2 * n - 1) ** (1 / 2) - 1) // 2))


t = int(input())
for _ in range(t):
	n = int(input())
	res = 0
	for a in range(2, 10 ** 9):
		a2 = pow(a, 2)
		if a2 <= 2 * n + 1:
			if (a2 - 1) % 2 == 0:
				b = (a2 - 1) // 2
				if a <= b <= n:
					c = a2 - b
					if b <= c <= n:
						res += 1
		else:
			break
	print(res)


try:
	import math
	test_case = int(input())
	for i in range(test_case):
		n = int(input())
		ans = (int(math.sqrt(2 * n - 1)) - 1) // 2
		print(ans)
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	m = int(pow(2 * n - 1, 0.5))
	ans = (m + 1) // 2
	print(ans - 1)


import math
ans = []
n = int(input())
while n > 0:
	cnt = 0
	num = int(input())
	a = math.sqrt(2 * num - 1)
	cnt = int((a - 1) / 2)
	print(cnt)
	n = n - 1


import math
answers = []

def solve(n):
	req = math.floor((math.sqrt(2 * n - 1) - 1) // 2)
	answers.append(req)
T = int(input())
while T:
	n = int(input())
	solve(n)
	T -= 1
for ans in answers:
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	n = math.floor(math.sqrt(n + n - 1))
	if n % 2 == 0:
		print(n // 2 - 1)
	else:
		print((n + 1) // 2 - 1)


import math
t = int(input())
while t > 0:
	n = int(input())
	nTuples = 0
	for a in range(3, math.ceil(math.sqrt(2 * n)), 2):
		nTuples += a * a + 1 & 1 == 0
	print(nTuples)
	t -= 1


import sys
import math
import bisect
import functools
from functools import lru_cache
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, ceil
from heapq import heappush, heappop, heapify
from collections import defaultdict as dd
from collections import Counter as cc
from bisect import bisect_left as bl
from bisect import bisect_right as br

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
sys.setrecursionlimit(100000000)
intinp = lambda : int(input().strip())
stripinp = lambda : input().strip()
fltarr = lambda : list(map(float, input().strip().split()))
intarr = lambda : list(map(int, input().strip().split()))
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
MOD = 1000000007
num_cases = intinp()
for _ in range(num_cases):
	n = intinp()
	print(math.ceil(int((2 * n - 1) ** 0.5) / 2) - 1)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	i = 3
	ans = 0
	while i <= n and (i * i - 1) // 2 <= n:
		if (i * i - 1) % 2 == 0 and (i * i - 1) // 2 >= i and (i * i - (i * i - 1) // 2 <= n):
			ans += 1
		i += 1
	print(ans)


ansl = []
for _ in range(int(input())):
	n = int(input())
	max2b_1 = 2 * n - 1
	max_root = int(max2b_1 ** 0.5)
	ans = (max_root - 1) // 2
	ansl.append(ans)
for a in ansl:
	print(a)


from collections import defaultdict
from itertools import accumulate
import bisect
import sys
import math
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353
LIST = []
i = 1
while True:
	if (i * i - 1) // 2 + 1 <= 1000000000:
		LIST.append((i * i - 1) // 2 + 1)
		i += 2
	else:
		break
for CASES in range(int(input())):
	n = int(input())
	limit = bisect.bisect_right(LIST, n)
	ans = limit - 1
	print(ans)


import sys
input = sys.stdin.readline
import math
t = int(input())
for you in range(t):
	n = int(input())
	z = math.sqrt(2 * n - 1)
	z = int(z)
	z = (z + 1) // 2
	z -= 1
	print(z)


import math
t = int(input())
while t > 0:
	a = int(input())
	print((int(math.sqrt(a + a - 1)) - 1) // 2)
	t -= 1


dep = []
from math import ceil, trunc, sqrt
t = int(input())
for i in range(t):
	n = int(input())
	res = 0
	res = ceil(trunc(sqrt(2 * (n - 1) + 1)) / 2 - 1)
	dep.append(res)
for i in dep:
	print(i)


def solve():
	x = int(input())
	t = int((2.0 * x - 1) ** 0.5)
	if t & 1:
		t += 1
	ans = t // 2 - 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


def check(num):
	if (num ** 2 + 1) // 2 <= n:
		return True
	return False
for nt in range(int(input())):
	n = int(input())
	low = 1
	high = n
	while low < high:
		mid = (low + high) // 2
		if not mid % 2:
			mid += 1
		if check(mid):
			low = mid + 1
		else:
			high = mid - 1
	if not low % 2:
		if check(low + 1):
			print(low // 2)
		else:
			print(low // 2 - 1)
	elif check(low):
		print(low // 2)
	else:
		print(low // 2 - 1)


import sys
from collections import Counter, defaultdict

def load_sys():
	return sys.stdin.readlines()

def load_local():
	with open('input.txt', 'r') as f:
		input = f.readlines()
	return input

def f(n):
	n = int((2 * n - 1) ** 0.5)
	if n % 2 == 0:
		n -= 1
	return max(1 + (n - 3) // 2, 0)
input = load_sys()
for i in range(1, len(input)):
	n = int(input[i])
	print(f(n))


from collections import defaultdict
import bisect
for _ in range(int(input())):
	n = int(input())
	a = (2 * n - 1) ** 0.5
	a = int(a)
	if a < 2:
		print(0)
	else:
		a -= 2
		ans = (a + 1) // 2
		print(ans)


import sys
import math
import bisect
fast_reader = sys.stdin.readline
fast_writer = sys.stdout.write

def input():
	return fast_reader().strip()

def print(*argv):
	fast_writer(' '.join((str(i) for i in argv)))
	fast_writer('\n')
import math
for T in range(int(input())):
	N = int(input())
	a = math.sqrt(2 * N - 1)
	print(int((a - 1) // 2))


from math import *
t = int(input())
for i in range(t):
	n = int(input())
	temp = int(sqrt(2 * n - 1))
	if n < 5:
		print(0)
	elif temp % 2 == 0:
		if ((temp - 1) ** 2 + 1) / 2 <= n:
			print(int(temp / 2) - 1)
	elif (temp ** 2 + 1) / 2 <= n:
		print(int(floor(temp / 2)))


for t in range(int(input())):
	n = int(input())
	x = int((2 * n + 1) ** 0.5)
	y = (x + 1) // 2 - 1
	if (x * x - 1) // 2 == n:
		y -= 1
	print(max(0, y))


from math import sqrt
t = int(input())
for _ in range(t):
	n = int(input())
	m = (int(sqrt(2 * n - 1)) - 1) // 2
	print(m)


from sys import stdin
nii = lambda : map(int, stdin.readline().split())
lnii = lambda : list(map(int, stdin.readline().split()))
t = int(input())
for tt in range(t):
	n = int(input())
	ans = 0
	num = 3
	while num ** 2 <= 2 * n - 1:
		ans += 1
		num += 2
	print(ans)


for s in [*open(0)][1:]:
	print(int((2 * int(s) - 1) ** 0.5 - 1) >> 1)


import sys
import math

def fn(n, k):
	if n % 2 == 0:
		ans = k % n
		if ans == 0:
			ans = n
		return ans
	if k == n:
		return 2
	if k < (n + 1) / 2:
		return 0
	return -1
	return (b + 1, t)

def f2(n):
	t = 0
	c = int(math.sqrt(n + n - 1))
	a = 3
	t = math.ceil(c / 2) - 1
	return t
input = sys.stdin.read()
data = list(map(int, input.split()))
t = data[0]
l = 0
for i in range(t):
	n = data[1 + l]
	l = l + 1
	print(f2(n))


import sys
input = sys.stdin.readline
import math
check = []
for i in range(1, 100000):
	check.append(1 + 2 * i * (i + 1))
t = int(input())
for f in range(t):
	import bisect
	n = int(input())
	print(bisect.bisect_right(check, n))


from math import sqrt, isclose, ceil
t = int(input())
for case in range(t):
	n = int(input())
	if n < 5:
		print(0)
	else:
		s = sqrt(2 * n - 1)
		c = int(s)
		print((c - 3) // 2 + 1)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = 1
	ans = 0
	while True:
		b = a * a // 2
		c = a * a - b
		if a <= b <= c <= n:
			ans += 1
		if c > n:
			break
		a += 2
	print(ans)


import math
num_cases = int(input())
for _ in range(num_cases):
	limit = int(input()) - 1
	largest_a = math.floor((limit * 2 + 1) ** 0.5)
	if largest_a % 2 == 0:
		largest_a -= 1
	print((largest_a - 1) // 2)


import math

def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
	n = read_int()
	if n <= 2:
		print(0)
	else:
		hi = math.floor(math.sqrt(n * 2 - 1))
		if hi % 2 == 0:
			hi -= 1
		print((hi - 1) // 2)


def main():
	tc = int(input())
	for _ in range(tc):
		r = int(input())
		occurance = 0
		m = 2
		n = 1
		c = m ** 2 + n ** 2
		while c <= r:
			a = m ** 2 - n ** 2
			b = 2 * m * n
			c = m ** 2 + n ** 2
			noobsc = a ** 2 - b
			if noobsc == c:
				occurance += 1
			m += 1
			n += 1
			c = m ** 2 + n ** 2
		print(occurance)
main()


import os
import sys
from io import BytesIO, IOBase
import math
import itertools
import bisect
import heapq

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	for i in range(2, n + 1):
		if primes[i]:
			for j in range(i + i, n + 1, i):
				primes[j] = False
	p = []
	for i in range(0, n + 1):
		if primes[i]:
			p.append(i)
	return p

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac
for _ in range(0, int(input())):
	n = int(input())
	t = 2 * n - 1
	t = int(t ** 0.5)
	print(math.ceil(t / 2) - 1)


import sys
input = sys.stdin.readline
import math

def solution(n):
	print((int(math.sqrt(n - 1 + n)) - 1) // 2)
T = int(input())
for t in range(T):
	n = int(input())
	solution(n)


t = int(input())
while t:
	n = int(input())
	a = (2 * n + 1) ** 0.5
	if a.is_integer():
		a = a // 2 - 1
	else:
		a = int(a)
		a = a // 2 if a % 2 else a // 2 - 1
	print(int(a))
	t -= 1


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		N = int(input())
		ok = 1
		ng = N
		mid = (ok + ng) // 2
		while ng - ok > 1:
			if (mid * mid + 1) // 2 <= N:
				ok = mid
			else:
				ng = mid
			mid = (ok + ng) // 2
		if ok < 3:
			print(0)
		else:
			print((ok + 1) // 2 - 1)
main()


import math
LO = 'abcdefghijklmnopqrstuvwxyz'
Mod = 1000000007

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	n = int(input())
	print((int(math.sqrt(n * 2 - 1)) + 1) // 2 - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = int(2 * n - 1) ** 0.5
	print(int(l - 1) // 2)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n < 5:
		print(0)
	else:
		ans = 0
		for i in range(3, int(math.sqrt(2 * n - 1)) + 1, 2):
			ans += 1
		print(ans)


import sys, functools, collections, bisect, math
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input().strip())
	c = 0
	l = 1
	h = n
	while l < h:
		mid = (l + h) // 2
		ele = 2 * mid + 1
		if (ele ** 2 - 1) // 2 + 1 <= n:
			l = mid + 1
		else:
			h = mid
	print(h - 1)


import math
t = int(input())
for u in range(t):
	n = int(input())
	left = 7
	right = 2 * n - 1
	if right <= left:
		print(0)
	else:
		start = math.ceil(7 ** 0.5)
		end = int(right ** 0.5)
		z = end - start + 1
		if not z & 1:
			print(z // 2)
		elif start & 1 or end & 1:
			print(z // 2 + 1)
		else:
			print(z // 2)


import io
import os
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right
oddSquares = []
for i in range(3, int(10 ** 5) + 1, 2):
	oddSquares.append(i * i)
assert 2 * 10 ** 9 - 1 <= oddSquares[-1]

def solveBrute(N):
	count = 0
	for c in range(1, N + 1):
		aa = 2 * c - 1
		if aa in oddSquares:
			count += 1
			b = c - 1
			a = int(aa ** 0.5)
			assert 1 <= a <= b <= c <= N
			assert a * a + b * b == c * c
			assert c == a * a - b
	return count

def solve(N):
	count = bisect_right(oddSquares, 2 * N - 1)
	return count
if False:
	for N in range(1, 100):
		(ans, ans1) = (solve(N), solveBrute(N))
		print(N, ans, ans1)
		assert ans == ans1
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	ans = solve(N)
	print(ans)


from math import ceil, sqrt

def solve():
	n = int(input().strip())
	a_lim = ceil(sqrt(1 + 2 * (n - 1)))
	if a_lim * a_lim != 1 + 2 * (n - 1):
		a_lim -= 1
	diff = a_lim - 3 + 1
	print(diff // 2 + a_lim % 2)
t = int(input().strip())
for _ in range(t):
	solve()


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return sorted(fac)

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
for _ in range(int(input())):
	n = int(input())
	count = 0
	i = 3
	while i * i <= 2 * n - 1:
		count += 1
		i += 2
	print(count)


(T,) = map(int, input().split())
Q = []
for i in range(T):
	(N,) = map(int, input().split())
	Q.append((i, N))
Q.sort(key=lambda x: x[1])
a = 1
cnt = 0
R = [0] * T
now = 0
while True:
	a += 1
	if a ** 2 % 2:
		b = (a ** 2 - 1) // 2
		c = b + 1
		if c > 10 ** 9:
			break
		if a ** 2 + b ** 2 == c ** 2:
			while now < len(Q) and Q[now][1] < c:
				R[Q[now][0]] = cnt
				now += 1
			cnt += 1
while now < len(Q) and Q[now][1] < c:
	R[Q[now][0]] = cnt
	now += 1
for r in R:
	print(r)


import sys
import math

def solve():
	n = int(sys.stdin.readline().rstrip())
	m = int(math.sqrt(n * 2 - 1))
	if m % 2 == 0:
		m -= 1
	res = (m - 3) // 2 + 1
	print(res)
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
	solve()


import math
t = int(input())

def get_answer(n):
	total = 0
	if n <= 4:
		return 0
	return (int(math.sqrt(2 * n - 1)) - 1) // 2
for _ in range(t):
	n = int(input())
	print(get_answer(n))


import math
t = int(input())
for j in range(t):
	n = int(input())
	print(math.floor((math.sqrt(2 * n - 1) - 1) / 2))


import math
from sys import stdin
input = stdin.readline

def main():
	test = int(input())
	for _ in range(test):
		n = int(input())
		k = math.floor(math.sqrt(2 * n - 1))
		ans = (k - 1) // 2
		print(ans)
main()


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return tmp[:x]

def err(x):
	print(x)
	exit()
for _ in range(inp()):
	n = inp()
	m = int(math.sqrt(2 * n - 1))
	print(max(0, (m - 3) // 2 + 1))


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = int(input())
for _ in range(t):
	n = ip()
	ans = 0
	i = 3
	while i * i <= 2 * n - 1:
		ans += 1
		i += 2
	print(ans)


t = int(input())
for q in range(t):
	n = int(input())
	z = int(2 ** 0.5 * (n - 0.5) ** 0.5)
	if z % 2 == 0:
		print(int(z / 2 - 1))
	else:
		print(int((z - 1) / 2))


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	f = int((2 * n - 1) ** 0.5)
	g = 3
	while g <= f:
		if g % 2 == 1:
			c += 1
		g += 1
	print(c)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

def A095861(n):
	return int((n * 2 - 1) ** 0.5) - 1 >> 1

def solve():
	return A095861(itg())

def main():
	for _ in range(itg()):
		print(solve())
DEBUG = 0
URL = 'https://codeforces.com/contest/1487/problem/D'
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
else:
	if DEBUG != 3:
		(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	if DEBUG:
		_print = print

		def print(*args, **kwargs):
			_print(*args, **kwargs)
			sys.stdout.flush()
	main()


import sys
import math
input = sys.stdin.readline
l = []
i = 3
while i * i <= 2000000000:
	l.append(i * i // 2 + 1)
	i += 2
t = int(input())
while t > 0:
	n = int(input())
	lo = 0
	r = len(l) - 1
	ans = 0
	p = -1
	while lo <= r:
		m = (lo + r) // 2
		if l[m] > n:
			r = m - 1
		else:
			ans = m + 1
			lo = m + 1
	print(ans)
	t -= 1


import math
iter = int(input())
for _ in range(iter):
	n = int(input())
	print((math.floor(math.sqrt(2 * n - 1)) + 1) // 2 - 1)


from math import isqrt

def solve(n):
	print((isqrt(2 * n - 1) - 1) // 2)
t = int(input())
for test in range(t):
	n = int(input())
	solve(n)


read = lambda : map(int, input().split())
t = int(input())
for _ in range(t):
	n = int(input())
	print((int((2 * n - 1) ** 0.5) - 1) // 2)