Chef played an interesting game yesterday. This game is played with two variables $X$ and $Y$; initially, $X = Y = 0$. Chef may make an arbitrary number of moves (including zero). In each move, he must perform the following process:
- Choose any positive integer $P$ such that $P \cdot P > Y$.
- Change $X$ to $P$.
- Add $P \cdot P$ to $Y$.
Unfortunately, Chef has a bad memory and he has forgotten the moves he made. He only remembers the value of $X$ after the game finished; let's denote it by $X_f$. Can you tell him the maximum possible number of moves he could have made in the game?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single integer $X_f$.

-----Output-----
For each test case, print a single line containing one integer — the maximum number of moves Chef could have made.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le X_f \le 10^9$

-----Example Input-----
3
3
8
9

-----Example Output-----
3
5
6

-----Explanation-----
Example case 2: One possible sequence of values of $X$ is $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 8$.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
def bs(val, l):
	i = 0
	j = len(l) - 1
	ans = -1
	while i <= j:
		mid = i + (j - i) // 2
		if l[mid] <= val:
			ans = mid
			i = mid + 1
		else:
			j = mid - 1
	return ans + 1

def bst(i, val):
	j = 100000000000
	ans = -1
	while i <= j:
		mid = i + (j - i) // 2
		if mid ** 2 > val:
			ans = mid
			j = mid - 1
		else:
			i = mid + 1
	return ans
e = 10 ** 9
l = [1]
sum = 1
while l[-1] <= e:
	x = bst(l[-1] + 1, sum)
	sum += x ** 2
	l.append(x)
t = int(input())
for _ in range(t):
	n = int(input())
	print(bs(n, l))


from math import sqrt, ceil
import time
from bisect import bisect_right
start_time = time.time()
a = []
x = 0
y = 0
while x <= 10 ** 9:
	x = int(sqrt(y)) + 1
	a.append(x)
	y += x * x
end_time = time.time()
for _ in range(int(input())):
	n = int(input())
	print(bisect_right(a, n))


import math

def binarySearch(arr, l, r, x):
	mid = (l + r) // 2
	if arr[mid] == x:
		return mid
	elif arr[mid] > x:
		return binarySearch(arr, l, mid - 1, x)
	elif arr[mid] < x and arr[mid + 1] > x:
		return mid
	else:
		return binarySearch(arr, mid + 1, r, x)

def vceil(k):
	if math.ceil(k) == k:
		return int(k + 1)
	else:
		return math.ceil(k)
dp = [1]
i = 1
sum = 0
while i <= 10 ** 9:
	sum += i ** 2
	i = math.sqrt(sum)
	i = vceil(i)
	dp.append(i)
t = int(input())
for _ in range(t):
	n = int(input())
	ans = binarySearch(dp, 0, len(dp), n)
	ans = ans + 1
	print(ans)


import math
test = int(input())
for _ in range(test):
	last = int(input())
	x = 0
	y = 0
	c = 0
	while True:
		if y >= last * last:
			print(c)
			break
		c += 1
		x = int(math.sqrt(y)) + 1
		y = y + x * x


a = [1, 5, 14, 30, 66, 147, 316, 640, 1316, 2685, 5389, 10865, 21890, 43794, 87894, 176103, 352503, 705339, 1410939, 2822283, 5644683, 11290059, 22586380, 45177389, 90362673, 180726709, 361467845, 722962014, 1445926558, 2891903234, 5783868963, 11567775667, 23135638583, 46271569608, 92543451489, 185087175589, 370174703113, 740349599513, 1480699709609, 2961401728890, 5922805611019, 11845613688143, 23691229216659, 47382461525155, 94764923639219, 189529852873203, 379059728863428, 758119484738277, 1516238988699177, 3032478012198573, 6064956028042173, 12129912122039757, 24259824405685918, 48519649093187567, 97039298227772211, 194078596977778807, 388157194397204432, 776314389397230816, 1552628779074933316]
t = int(input())
for _ in range(t):
	n = int(input())
	sq = n ** 2
	ans = 1
	for i in range(len(a)):
		if sq > a[i]:
			ans += 1
		else:
			break
	print(ans)


from collections import defaultdict as dd
from math import sqrt
d = dd(int)
x = 0
y = 0
cou = 0
l = []
for i in range(100):
	a = int(sqrt(y))
	s = (a + 1) ** 2
	d[x] = cou
	l.append(x)
	x = a + 1
	y += s
	cou += 1
t = int(input())
while t:
	n = int(input())
	for i in range(100):
		if l[i] > n:
			break
	print(d[l[i - 1]])
	t -= 1


def f(n):
	x = 1
	c = 1
	y = 1
	r = n ** 2
	while True:
		if r <= y:
			print(c)
			break
		else:
			c += 1
			x = int(y ** (1 / 2)) + 1
			y += x * x
for _ in range(int(input())):
	n = int(input())
	f(n)


import math
t = int(input())
for i in range(t):
	n = int(input())
	x = 0
	y = 0
	count = 0
	while x <= n:
		tmp = 1 + int(math.sqrt(y))
		x = tmp
		y += tmp * tmp
		count += 1
	print(count - 1)


import math
t = int(input())
for _ in range(t):
	xf = int(input())
	ans = 0
	(x, y) = (0, 0)
	while x <= xf:
		p = int(math.sqrt(y))
		if p * p > y:
			x = p
			y = y + p * p
			ans = ans + 1
		else:
			x = p + 1
			y = y + (p + 1) * (p + 1)
			ans = ans + 1
	if x <= xf:
		print(ans)
	else:
		print(ans - 1)


l = [1, 2, 3, 4, 6, 9, 13, 18, 26, 37, 52, 74, 105, 148, 210, 297, 420, 594, 840, 1188, 1680, 2376, 3361, 4753, 6722, 9506, 13444, 19013, 26888, 38026, 53777, 76052, 107554, 152105, 215109, 304210, 430218, 608420, 860436, 1216841, 1720873, 2433682, 3441746, 4867364, 6883492, 9734728, 13766985, 19469457, 27533970, 38938914, 55067940, 77877828, 110135881, 155755657, 220271762, 311511314, 440543525, 623022628, 881087050, 1246045256]
n = len(l)
for _ in range(int(input())):
	steps = 0
	x = int(input())
	for i in range(n):
		if l[i] > x:
			break
		steps += 1
	print(steps)


import math
T = int(input())
for i in range(T):
	x = int(input())
	(temp, count, y) = (0, 0, 0)
	p = 0
	while temp <= x:
		p = int(math.sqrt(y))
		if p * p > y:
			temp = p
			y += p * p
			count += 1
		else:
			p += 1
			temp = p
			y += p * p
			count += 1
	if temp > x:
		print(count - 1)
	elif temp <= x:
		print(count)


T = int(input())
i = 0
for i in range(T):
	Xf = int(input())
	p = 0
	y = 0
	count = 0
	while p <= Xf:
		y = y + p * p
		p = int(y ** 0.5) + 1
		count = count + 1
	print(count - 1)


import math
T = int(input())
for z in range(T):
	X = int(input())
	(y, x1, cnt) = (0, 0, 0)
	while int(math.sqrt(y)) + 1 <= X:
		x1 = int(math.sqrt(y)) + 1
		y += int(x1 * x1)
		cnt += 1
	print(cnt)


from math import sqrt, ceil
t = int(input())
for i in range(t):
	x = int(input())
	y = 0
	count = 0
	next = 0
	while next <= x:
		if next * next > y:
			count += 1
			y += next * next
			next = ceil(sqrt(y))
		else:
			next += 1
	print(count)


import sys
from math import sqrt
try:
	sys.stdin = open('inp.txt', 'r')
except:
	pass

def helper():
	pass
t = int(input())
for _ in range(t):
	n = int(input())
	x = 0
	y = 0
	k = 0
	while x <= n:
		a = int(sqrt(y))
		a += 1
		x = a
		y += a * a
		k += 1
	print(k - 1)


import math
T = int(input())
for i in range(T):
	N = int(input())
	(s, x, y, c) = (1, 0, 0, 0)
	while s * s > y and s <= N:
		y = y + s * s
		x = s
		c += 1
		s = math.floor(math.sqrt(y)) + 1
	print(c)


import math
t = int(input())
for T in range(t):
	xf = int(input())
	(x, y) = (0, 0)
	p = 1
	val = 0
	while x <= xf:
		x = p
		y += p * p
		p = math.ceil(math.sqrt(y))
		val += 1
	print(val - 2)


from math import ceil
for i in range(int(input())):
	xf = int(input())
	x = 0
	y = 0
	p = 1
	step = 0
	while x <= xf:
		x = p
		y += p * p
		p = ceil(y ** 0.5)
		step += 1
	print(step - 2)


import math
t = int(input())
while t > 0:
	t -= 1
	xf = int(input())
	x = 0
	y = 0
	p = 0
	count = 0
	while xf >= x:
		p = int(math.sqrt(y) + 1)
		y += p * p
		x = p
		count += 1
	print(count - 1)


import math
tcase = int(input())
while tcase > 0:
	tcase -= 1
	xf = int(input())
	(x, y, cnt) = (0, 0, 0)
	while x <= xf:
		temp = int(math.sqrt(y))
		temp += 1
		cnt += 1
		x = temp
		y += temp * temp
	print(cnt - 1)


from bisect import bisect_left
from math import sqrt, ceil, floor
t = int(input())
x = [0, 1]
y = 1
while x[-1] <= 10 ** 9:
	nxt = floor(sqrt(y)) + 1
	x.append(nxt)
	y += nxt ** 2
while t:
	n = int(input())
	a = bisect_left(x, n)
	if a > 0:
		if x[a] == n:
			print(a)
		else:
			print(a - 1)
	t -= 1


from math import floor, sqrt
test = int(input())
for tt in range(0, test):
	n = int(input())
	x = 0
	y = 0
	c = 0
	while x <= n:
		d = floor(sqrt(y))
		x = d + 1
		y = y + x * x
		c = c + 1
	print(c - 1)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	y = 0
	ans = 0
	while y < n * n:
		ceil = math.ceil(y ** 0.5)
		p = ceil if ceil > y ** 0.5 else ceil + 1
		y += p * p
		ans += 1
	print(ans)


from math import sqrt, ceil
t = int(input())
for i in range(t):
	x = int(input())
	y = 0
	c = 0
	n = 0
	while n <= x:
		if n * n > y:
			c += 1
			y += n * n
			n = ceil(sqrt(y))
		else:
			n += 1
	print(c)


import math
l = [0, 1, 2, 3, 4, 6, 9, 13]
s = 316
while l[-1] < 10 ** 9:
	l.append(math.floor(math.sqrt(s)) + 1)
	s += l[-1] ** 2
n = int(input())
while n > 0:
	n -= 1
	a = int(input())
	c = 0
	for i in l:
		if i <= a:
			c += 1
		else:
			break
	print(c - 1)


from math import sqrt
T = int(input())
ans = []
for _ in range(T):
	X = int(input())
	count = 0
	x = 0
	y = 0
	while x <= X:
		p = int(sqrt(y))
		count += 1
		if p * p > y:
			x = p
			y += p ** 2
		else:
			x = p + 1
			y += (p + 1) ** 2
	if x <= X:
		ans.append(count)
	else:
		ans.append(count - 1)
for i in ans:
	print(i)


import math as ma
import bisect

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

def nu():
	return int(input())

def li():
	return input().split()

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

def fli():
	return [float(x) for x in input().split()]
a = [0] * 60
pre = 0
for i in range(1, 60):
	lo = 0
	hi = int(1000000000.0)
	ans = 0
	while lo <= hi:
		mid = (lo + hi) // 2
		if mid * mid > pre:
			ans = mid
			hi = mid - 1
		else:
			lo = mid + 1
	pre += ans * ans
	a[i] = ans
t = nu()
for i in range(t):
	x = nu()
	it = bisect.bisect(a, x)
	print(it - 1)


l = []
x = 0
y = 0
while x < 10 ** 9:
	x = int(y ** 0.5) + 1
	if x ** 2 > y:
		l.append(x)
		y += x * x
for i in range(int(input())):
	xf = int(input())
	for j in range(60):
		if l[j] == xf:
			print(j + 1)
			break
		elif l[j] > xf:
			print(j)
			break


import math
t = int(input())
for _ in range(t):
	xfinal = int(input())
	xfinalsquare = xfinal * xfinal
	y = 1
	x = 1
	moves = 1
	while True:
		if xfinalsquare <= y:
			break
		moves += 1
		x = math.floor(math.sqrt(y)) + 1
		y += x * x
	print(moves)


import math
t = int(input())
for i in range(t):
	n = int(input())
	(num, x, y, count) = (1, 0, 0, 0)
	while num * num > y and num <= n:
		y = y + num * num
		x = num
		count += 1
		num = math.floor(math.sqrt(y)) + 1
	print(count)


from math import sqrt

def solve():
	n = int(input())
	(ct, p) = (0, 1)
	(x, y) = (0, 0)
	while x < n:
		y = y + p * p
		x = p
		p = int(sqrt(y)) + 1
		ct = ct + 1
		if y >= n * n:
			break
	print(ct)
T = int(input())
for p in range(T):
	solve()


import math
from bisect import bisect_right as br
a = [1]
(x, y) = (1, 1)
while x < 10 ** 9 + 1:
	x = int(math.sqrt(y)) + 1
	a.append(x)
	y += x ** 2
t = int(input())
for _ in range(t):
	n = int(input())
	print(br(a, n))


import math
T = int(input())
for x in range(T):
	Xf = int(input())
	sum = 0
	count = 0
	while sum < Xf * Xf:
		p = math.ceil(math.sqrt(sum)) if math.ceil(math.sqrt(sum)) > math.sqrt(sum) else math.ceil(math.sqrt(sum)) + 1
		sum += p * p
		count += 1
	print(count)


def binary(l, key):
	first = 0
	last = len(l) - 1
	found = False
	res = []
	while first <= last and (not found):
		midpoint = (first + last) // 2
		if l[midpoint] == key:
			res.append(67)
			res.append(midpoint)
			return res
		elif key < l[midpoint]:
			last = midpoint - 1
		else:
			first = midpoint + 1
	res.append(68)
	if key < l[first]:
		res.append(first - 1)
	else:
		res.append(first)
	return res
import math
mydict = [0]
(x, y) = (0, 0)
while x < 1000000000:
	temp = math.ceil(y ** 0.5)
	if temp ** 2 == y:
		temp += 1
	x = temp
	y += temp ** 2
	mydict.append(x)
t = int(input())
for zz in range(t):
	num = int(input())
	tempo = binary(mydict, num)
	if tempo[0] == 67:
		print(tempo[1])
	else:
		print(tempo[1])


from math import ceil
from math import sqrt

def getList():
	xy = []
	xy.append(0)
	x = 0
	y = 0
	for i in range(1, 100):
		p = ceil(sqrt(y))
		if p ** 2 == y:
			p += 1
		x = p
		y += p ** 2
		xy.append(x)
	return xy
t = int(input())
result = getList()
while t > 0:
	x = int(input())
	for i in range(0, 100):
		if result[i] > x:
			print(i - 1)
			break
		elif result[i] == x:
			print(i)
			break
	t -= 1


import math
t = int(input())
for _ in range(t):
	xf = int(input())
	x = 0
	y = 0
	c = 0
	p = 0
	while x <= xf:
		a = int(math.sqrt(y))
		if a == int(a):
			p = a + 1
		else:
			p = math.ceil(a)
		x = p
		y += p * p
		c += 1
	print(c - 1)


from math import sqrt
for i in range(int(input())):
	xf = int(input())
	if xf == 0:
		print(0)
	else:
		x = 1
		y = 1
		m = 1
		while True:
			if x == xf:
				print(m)
				break
			elif x > xf:
				print(m - 1)
				break
			m += 1
			x = int(sqrt(y)) + 1
			y += x * x


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	j = 0
	(x, y) = (0, 0)
	k = 0
	while x != n:
		j += 1
		if j <= n:
			x = j
		if y >= j * j:
			j = int(sqrt(y))
			continue
		if y + j * j < n * n and x != n:
			y += j * j
		else:
			x = n
		k += 1
	print(k)


Xs = [0, 1, 2, 3, 4, 6, 9, 13, 18, 26, 37, 52, 74, 105, 148, 210, 297, 420, 594, 840, 1188, 1680, 2376, 3361, 4753, 6722, 9506, 13444, 19013, 26888, 38026, 53777, 76052, 107554, 152105, 215109, 304210, 430218, 608420, 860436, 1216841, 1720873, 2433682, 3441746, 4867364, 6883492, 9734728, 13766985, 19469457, 27533970, 38938914, 55067940, 77877828, 110135881, 155755657, 220271762, 311511314, 440543525, 623022628, 881087050]
Ys = [0, 1, 5, 14, 30, 66, 147, 316, 640, 1316, 2685, 5389, 10865, 21890, 43794, 87894, 176103, 352503, 705339, 1410939, 2822283, 5644683, 11290059, 22586380, 45177389, 90362673, 180726709, 361467845, 722962014, 1445926558, 2891903234, 5783868963, 11567775667, 23135638583, 46271569608, 92543451489, 185087175589, 370174703113, 740349599513, 1480699709609, 2961401728890, 5922805611019, 11845613688143, 23691229216659, 47382461525155, 94764923639219, 189529852873203, 379059728863428, 758119484738277, 1516238988699177, 3032478012198573, 6064956028042173, 12129912122039757, 24259824405685918, 48519649093187567, 97039298227772211, 194078596977778807, 388157194397204432, 776314389397230816, 1552628779074933316]

def find_X_index(Xf, Xs):
	r = 0
	l = len(Xs) - 1
	pm = -1
	while r < l:
		m = (r + l) // 2
		if m == pm:
			break
		xm = Xs[m]
		if Xf <= xm:
			l = m
		else:
			r = m
		pm = m
	return r
for T in range(int(input().strip())):
	X = int(input().strip())
	P = X ** 2
	i = find_X_index(X, Xs)
	if X == Xs[i]:
		print(i)
	else:
		while i > 0 and Ys[i] >= P:
			i -= 1
		print(i + 1)


from bisect import bisect_right
rn = [1, 2, 3, 4, 6, 9, 13, 18, 26, 37, 52, 74, 105, 148, 210, 297, 420, 594, 840, 1188, 1680, 2376, 3361, 4753, 6722, 9506, 13444, 19013, 26888, 38026, 53777, 76052, 107554, 152105, 215109, 304210, 430218, 608420, 860436, 1216841, 1720873, 2433682, 3441746, 4867364, 6883492, 9734728, 13766985, 19469457, 27533970, 38938914, 55067940, 77877828, 110135881, 155755657, 220271762, 311511314, 440543525, 623022628, 881087050]
t = int(input())
while t > 0:
	t = t - 1
	print(bisect_right(rn, int(input())))


for _ in range(int(input())):
	num = int(input())
	moves = 0
	(x, y) = (0, 0)
	while x <= num:
		x = int(y ** 0.5) + 1
		y += x * x
		moves += 1
	print(moves - 1)


import math
for _ in range(int(input())):
	tt = int(input())
	x = y = moves = 0
	while x < tt and y < tt ** 2:
		x = math.floor(math.sqrt(y)) + 1
		y = y + x ** 2
		moves += 1
	print(moves)


import math
t = int(input())
a = []
k = 0
for i in range(70):
	l = math.floor(k ** 0.5) + 1
	a.append(l)
	k += l ** 2
while t > 0:
	x = int(input())
	for i in range(70):
		if x < a[i]:
			index = i
			break
	print(index)
	t = t - 1


l = [1, 5, 14, 30, 66, 147, 316, 640, 1316, 2685, 5389, 10865, 21890, 43794, 87894, 176103, 352503, 705339, 1410939, 2822283, 5644683, 11290059, 22586380, 45177389, 90362673, 180726709, 361467845, 722962014, 1445926558, 2891903234, 5783868963, 11567775667, 23135638583, 46271569608, 92543451489, 185087175589, 370174703113, 740349599513, 1480699709609, 2961401728890, 5922805611019, 11845613688143, 23691229216659, 47382461525155, 94764923639219, 189529852873203, 379059728863428, 758119484738277, 1516238988699177, 3032478012198573, 6064956028042173, 12129912122039757, 24259824405685918, 48519649093187567, 97039298227772211, 194078596977778807, 388157194397204432, 776314389397230816, 1552628779074933316]
for _ in range(int(input())):
	n = int(input())
	x = 0
	a = n * n
	s = 0
	while l[x] < a:
		x += 1
	print(x + 1)


import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	x = 0
	y = 0
	ans = 0
	while x <= n:
		z = int(math.sqrt(y))
		z += 1
		y += z * z
		x = z
		ans += 1
	print(ans - 1)


import math
try:
	t = int(input())
	while t > 0:
		t -= 1
		xf = int(input())
		x = 0
		y = 0
		p = 0
		count = 0
		while xf >= x:
			p = int(math.sqrt(y) + 1)
			y += p * p
			x = p
			count += 1
		print(count - 1)
except:
	pass


import math
for _ in range(int(input())):
	xf = int(input())
	x = 0
	y = 0
	p = 1
	i = 0
	while x <= xf:
		i += 1
		x = p
		y += pow(p, 2)
		p = math.sqrt(y)
		if p % 1:
			p = int(math.ceil(p))
		else:
			p = p + 1
	print(i - 1)


def sqrt(n):
	return int(n ** 0.5) + 1

def answer():
	(ans, x, y) = (0, 0, 0)
	while sqrt(y) <= n:
		p = sqrt(y)
		ans += 1
		y += p * p
	return ans
for T in range(int(input())):
	n = int(input())
	print(answer())


import math
t = int(input())
while t:
	n = int(input())
	res = 0
	x = 0
	y = 0
	while x <= n:
		tmp = int(math.sqrt(y))
		tmp += 1
		y += tmp * tmp
		x = tmp
		res += 1
	print(res - 1)
	t -= 1


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	y = 0
	c = 0
	while True:
		if y >= n * n:
			break
		s = int(pow(y, 0.5) + 1)
		y += s * s
		c += 1
	print(c)


import math
n = int(input())
for i in range(n):
	m = int(input())
	(i, y) = (1, 1)
	count = 1
	while i < m:
		n = math.sqrt(y)
		i = n // 1 + 1
		if i <= m:
			y += i ** 2
			count += 1
	print(count)


import math

def fun():
	n = int(input())
	x = 0
	y = 0
	coun = 0
	while x < n:
		t = y ** 0.5
		t = math.floor(t)
		if t ** 2 <= y:
			t += 1
		x = t
		y += t ** 2
		coun += 1
	if x > n:
		coun -= 1
	print(coun)
nn = int(input())
for ii in range(nn):
	fun()


X_array = [1, 2, 3, 4, 6, 9, 13, 18, 26, 37, 52, 74, 105, 148, 210, 297, 420, 594, 840, 1188, 1680, 2376, 3361, 4753, 6722, 9506, 13444, 19013, 26888, 38026, 53777, 76052, 107554, 152105, 215109, 304210, 430218, 608420, 860436, 1216841, 1720873, 2433682, 3441746, 4867364, 6883492, 9734728, 13766985, 19469457, 27533970, 38938914, 55067940, 77877828, 110135881, 155755657, 220271762, 311511314, 440543525, 623022628, 881087050, 1246045256, 1762174101, 2492090513, 3524348202, 4984181026, 7048696404, 9968362052, 14097392809]
for _ in range(int(input())):
	N = int(input())
	X = 0
	Y = 0
	count = 0
	while N > X:
		P = X_array[count]
		X = P
		Y += P * P
		count += 1
	if X > N:
		count -= 1
	print(count)


import math
tc = int(input())
for _ in range(tc):
	Xf = int(input())
	Y = 0
	X = 0
	moves = 0
	P = 1
	while P <= Xf:
		if P ** 2 > Y:
			Y += P ** 2
			X = P
			moves = moves + 1
		P = int(math.sqrt(Y)) + 1
	print(moves)


try:
	from math import sqrt
	from bisect import bisect
	x = 0
	y = 0
	ans = [0]
	while x <= 10 ** 9:
		x = int(sqrt(y)) + 1
		y += x * x
		ans.append(x)
	for _ in range(int(input())):
		x = int(input())
		y = bisect(ans, x) - 1
		print(y)
except EOFError:
	pass


from math import sqrt
x = [1]
p = []
a = x[-1]
while sqrt(a) < 10 ** 9:
	root = sqrt(a)
	if int(root) != root:
		root = int(root) + 1
		p.append(root)
		b = root ** 2 + a
		x.append(b)
		a = b
	else:
		root = int(root)
		p.append(root)
		b = root ** 2 + a
		x.append(b)
		a = b
for _ in range(int(input())):
	xf = int(input())
	ans = 0
	for i in p:
		if i > xf:
			break
		else:
			ans += 1
	print(ans)


import math
from bisect import bisect_right
ls = [1]
(X, Y) = (1, 1)
while X < 10 ** 9 + 1:
	X = int(math.sqrt(Y)) + 1
	ls.append(X)
	Y += X ** 2
tc = int(input())
for _ in range(tc):
	Xf = int(input())
	moves = bisect_right(ls, Xf)
	print(moves)


import math
t = int(input())
while t != 0:
	n = int(input())
	x = int(0)
	y = int(0)
	ans = int(0)
	while x <= n:
		p = math.sqrt(y)
		p = int(p + 1)
		y = int(y + p * p)
		x = int(p)
		ans = ans + 1
	print(ans - 1)
	t = t - 1


for _ in range(int(input())):
	xf = int(input())
	x = 0
	y = 0
	op = -1
	while x <= xf:
		p = int(pow(y, 0.5)) + 1
		x = p
		sq = p * p
		y += sq
		op += 1
	print(op)


d = {}
n = 1000000000
s = 0
high = n ** 2
low = 1
cnt = 0
while s < high:
	s += low ** 2
	cnt += 1
	d[low] = cnt
	low = int((s + 1) ** 0.5) + 1
l = list(d.keys())
t = int(input())
for _ in range(t):
	n = int(input())
	if n in d.keys():
		ans = d[n]
	else:
		fl = 0
		for i in range(len(l)):
			if fl == 1:
				break
			elif l[i] < n:
				continue
			else:
				ans = d[l[i - 1]]
				fl = 1
		if fl == 0:
			ans = d[l[-1]]
	print(ans)


import math
T = int(input())
for i in range(T):
	X = int(input())
	(y, k, t) = (0, 0, 0)
	while int(math.sqrt(y)) + 1 <= X:
		k = int(math.sqrt(y)) + 1
		y += int(k * k)
		t = t + 1
	print(t)


import math
for _ in range(int(input())):
	xf = int(input())
	x = y = c = 0
	while x < xf:
		p = math.floor(math.sqrt(y)) + 1
		if p > xf:
			c -= 1
		x = p
		y += p * p
		c += 1
	print(c)


import math
T = int(input())
for t in range(T):
	xf = int(input())
	(x, y, count) = (0, 0, 0)
	while x <= xf:
		p = int(math.sqrt(y))
		p += 1
		x = p
		y += p * p
		count += 1
	print(count - 1)


import math

def nextPerfectSquare(N):
	nextN = math.floor(math.sqrt(N)) + 1
	return nextN
t = int(input())
for _ in range(t):
	n = int(input())
	x = 0
	y = 0
	p = 60
	i = 0
	st = 0
	while x <= n:
		p = nextPerfectSquare(y)
		x = p
		y = y + p * p
		st = st + 1
	print(st - 1)


l = [0]
x = 0
sumi = 0
while x <= pow(10, 9):
	x = int(pow(sumi, 0.5)) + 1
	l.append(x)
	sumi += x * x
t = int(input())
for i in range(t):
	x = int(input())
	for j in range(len(l)):
		if l[j] == x:
			print(j)
			break
		elif l[j] > x:
			print(j - 1)
			break


t = int(input())
for _ in range(t):
	xf = int(input())
	(c, x, y) = (0, 0, 0)
	while x <= xf:
		p = int(y ** 0.5)
		p += 1
		y = y + p * p
		x = p
		c += 1
	print(c - 1)