Little Ashish is doing internship at multiple places. Instead of giving parties to his friends he decided to donate candies to children. He likes solving puzzles and playing games. Hence he plays a small game. Suppose there are $N$ children. The rules of the game are:  

The $i^{{th}}$ child gets $i^2$ candies ($1\leq i\leq N$).  

The $y^{th}$ child cannot get a candy until and unless all the children before him ($1\leq i<y$) gets candies according to rule number $1$.  

One of his jealous friends, Pipi, asks him "Given ${X}$ (the number of candies) how many children will you be able to serve?". Little Ashish fears calculations and cannot solve this problem so he leaves this problem to the worthy programmers of the world. Help little Ashish in finding the solution.  

Input Format 

The first line contains ${T}$ i.e. number of test cases. 

${T}$ lines follow, each line containing an integer ${X}$.  

Output Format 

For each testcase, print the output that little Ashish wants in one line.   

Constraints 

$1\leq T\leq10000$ 

$1\leq X\leq10^{16}$  

Note: If the $i^{{th}}$ child doesn't get $i^2$ number of candies then it's not counted as a successful donation  

Sample Input  

3
1
5
13

Sample Output  

1  
2  
2  

Explanation  

For $X=1$. Only the $1^{st}$ child can get the candy (i.e. $1^{2}$ candy) and no other child.  
For $X=5$. Both the $1^{st}$($1^{2}$ candies) and the $2^{nd}$($2^{2}$ candies) children can get the candies.  
For $X=13$. Since the $3^{rd}$ child will get only 8 candies following the rule it won't be counted as a successful donation. Only the $1^{st}$ and the $2^{nd}$ children can get 1 and 4 candies respectively.

Difficulty: MEDIUM_HARD
Tags: Number theory

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	l = 0
	r = n
	while r - l > 1:
		m = (l + r) // 2
		if m * (m + 1) * (2 * m + 1) // 6 > n:
			r = m
		else:
			l = m
	if r * (r + 1) * (2 * r + 1) <= n * 6:
		print(r)
	else:
		print(l)


T = int(input())
for t in range(T):
	X = int(input())
	(l, r) = (1, 10 ** 6)
	while r - l > 1:
		m = (l + r) // 2
		if m * (m + 1) * (2 * m + 1) // 6 <= X:
			l = m
		else:
			r = m
	print(l)


import bisect
T = int(input())
X = [int(input()) for _ in range(T)]
MaxX = max(X)
(S, i) = ([0], 1)
while S[-1] < MaxX:
	S.append(S[-1] + i * i)
	i += 1
for x in X:
	print(bisect.bisect(S, x) - 1)


t = int(input())
for _ in range(t):
	x = int(input())
	(low, high) = (0, 10 ** 7)
	while high - low > 1:
		mid = low + high >> 1
		val = mid * (mid + 1) * (2 * mid + 1) // 6
		if val <= x:
			low = mid
		else:
			high = mid
	print(low)


def do(a):
	about = 0.5 * (0.48075 * (1.7321 * (3888 * a ** 2 - 1) ** 0.5 + 108 * a) ** (1 / 3) + 0.69336 / (1.7321 * (3888 * a ** 2 - 1) ** 0.5 + 108 * a) ** (1 / 3) - 1)
	about = int(about) - 1
	for x in range(about, 10 ** 50, 1):
		if (x + 1) * (x + 2) * (2 * (x + 1) + 1) / 6 > a:
			break
	return x
tcs = int(input())
for i in range(tcs):
	print(do(int(input())))


T = int(input())
f = lambda x: x * (x + 1) * (2 * x + 1) // 6
for i in range(T):
	n = int(input())
	(ub, lb) = (100000000, 1)
	while ub - lb > 1:
		mid = (ub + lb) // 2
		if f(mid) <= n:
			lb = mid
		else:
			ub = mid
	print(lb)


import sys

def InputIterator():
	for line in sys.stdin:
		for value in line.split():
			yield value
inp = InputIterator()
T = int(next(inp))
for t in range(T):
	X = int(next(inp))
	(L, R) = (1, 10 ** 6)
	while L < R:
		M = (L + R + 1) // 2
		Q = (2 * M ** 3 + 3 * M ** 2 + M) // 6
		if Q > X:
			R = M - 1
		else:
			L = M
	print(L)


n = 10 ** 6
li = [0] * n
for i in range(n):
	li[i] = i * (i + 1) * (2 * i + 1) // 6

def binSearch(a):
	(lo, hi) = (0, len(li))
	while lo < hi:
		mid = (lo + hi) // 2
		if li[mid - 1] <= a and a < li[mid]:
			return mid - 1
		elif li[mid] < a:
			lo = mid + 1
		else:
			hi = mid
	return lo
for _ in range(int(input())):
	print(binSearch(int(input())))


t = int(input())
for bk in range(t):
	n = int(input())
	a = n
	n *= 3
	k = int(pow(n, 1 / 3))
	while k * (k + 1) * (1 + 2 * k) // 6 <= a:
		k += 1
	print(k - 1)


from math import sqrt

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

def binary_search(iMin, iMax, t, func):
	while True:
		if iMax < iMin:
			return iMax
		m = (iMin + iMax) // 2
		y = f(m)
		if y < t:
			iMin = m + 1
		elif t < y:
			iMax = m - 1
		else:
			return m

def solve(p):
	Y = 6 * p
	return binary_search(0, 391486, Y, f)
T = int(input())
for _ in range(T):
	p = int(input())
	print(solve(p))


def f(x):
	return (2 * x ** 3 + 3 * x ** 2 + x) / 6

def approx(N, l, u, lv, uv):
	if u - l == 1:
		if uv == N:
			return u
		else:
			return l
	m = (l + u) // 2
	mv = f(m)
	if mv < N:
		return approx(N, m, u, mv, uv)
	else:
		return approx(N, l, m, lv, mv)

def solve(N):
	upper = int((3 * N) ** 0.5) + 1
	lower = 0
	return approx(N, lower, upper, f(lower), f(upper))
for _ in range(0, int(input())):
	print(solve(int(input())))


for i in range(int(input())):
	x = 3 * int(input())
	n = int(x ** (1 / 3)) - 1
	if (n + 1) * (n + 2) * (2 * n + 3) > x * 2:
		print(n)
	else:
		print(n + 1)


t = int(input())

def s2(n):
	return n * (n + 1) * (2 * n + 1) // 6
for i in range(t):
	n = int(input())
	l = 0
	r = n
	while l < r:
		m = (l + r) // 2
		if s2(m + 1) <= n:
			l = m + 1
		else:
			r = m
	print(l)


from bisect import bisect_left
a = [0]
sum = 0
for i in range(1, 500001):
	sum += i * i
	a.append(sum)
for _ in range(int(input())):
	x = int(input())
	i = bisect_left(a, x)
	if a[i] == x:
		print(i)
	else:
		print(i - 1)


import math
import sys
count = sys.stdin.readline()
for i in range(int(count)):
	line = sys.stdin.readline()
	approx = int(math.pow(3 * int(line), 1 / 3))
	lowbound = approx - 2
	upperbound = approx + 2
	for i in range(lowbound, upperbound):
		if i * (i + 1) * (2 * i + 1) / 6 > int(line):
			print(i - 1)
			break


def cand(n):
	return n * (n + 1) * (1 + 2 * n) // 6

def find(x):
	hi = 10 ** 6
	lo = 0
	while lo + 1 < hi:
		m = (hi + lo) // 2
		v = cand(m)
		if x == v:
			return m
		if x > v:
			lo = m
		else:
			hi = m
	return lo
for case in range(int(input())):
	print(find(int(input())))


candies = []
for t in range(int(input())):
	candies.append(int(input()))
scand = sorted(candies)
countGivenCandies = 0
countChilds = 0
res = {}
while scand:
	countChilds += 1
	countGivenCandies += countChilds ** 2
	while scand and countGivenCandies > scand[0]:
		res[scand.pop(0)] = countChilds - 1
for c in candies:
	print(res[c])


import bisect

def init(Y, M):
	Y.clear()
	(i, y) = (0, 0)
	while y <= M:
		Y.append(y)
		i += 1
		y += i * i
T = int(input())
X = [int(input()) for _ in range(T)]
Y = []
init(Y, max(X))
for x in X:
	print(bisect.bisect(Y, x) - 1)


import math

def main():
	number_of_test_cases = int(input())
	for test_case in range(number_of_test_cases):
		number_of_candies = int(input())
		i = 1
		n = int(math.exp((math.log(3) + math.log(number_of_candies)) / 3))
		candies = int(n * (n + 1) * (2 * n + 1) / 6)
		while candies > number_of_candies:
			n -= 1
			candies = int(n * (n + 1) * (2 * n + 1) / 6)
		print(n)
main()


t = int(input())
for i in range(t):
	x = int(input())
	n = int((3 * x) ** (1 / 3))
	while n * (n + 1) * (2 * n + 1) // 6 > x:
		n -= 1
	print(n)


import sys
data = []
for line in sys.stdin:
	data.append(int(line))
del data[0]

def sumsquares(n):
	return n * (n + 1) * (2 * n + 1) / 6

def numchild(x, num):
	while x >= 0:
		x -= num * num
		num += 1
	return num - 2

def altnumchild(x):
	test = 5000
	while x > sumsquares(test):
		test += 5000
	return numchild(x - sumsquares(test - 5000 - 1), test - 5000)
for i in range(len(data)):
	print(altnumchild(data[i]))


a = int(input())

def S(y):
	return y * (y + 1) * (2 * y + 1) / 6

def answer(X):
	L = 1
	R = 1000000
	while R - L > 1:
		M = (L + R) / 2
		if S(M) <= X:
			L = M
		else:
			R = M
	a = int(L)
	while S(a) <= X:
		a += 1
	return a - 1
for _ in range(0, a):
	b = int(input())
	print(answer(b))


from math import floor, sqrt
sr3 = sqrt(3.0)
cr3 = 3.0 ** (1 / 3.0)
cr32 = 3.0 ** (2 / 3.0)
for t in range(int(input())):
	x = int(input())
	k = (sr3 * sqrt(3888 * x * x - 1) + 108 * x) ** (1.0 / 3.0)
	r = 0.5 * (k / cr32 + 1 / (k * cr3) - 1)
	print(floor(round(r, 5)))


import math
T = int(input())

def useful(n):
	n = n * (n + 1) * (2 * n + 1) / 6
	return n
for i in range(1, T + 1):
	X = int(input())
	if X == 1:
		print(1)
		continue
	final = X
	initial = 0
	while 1:
		ind = math.floor((initial + final) / 2)
		if useful(ind) <= X and useful(ind + 1) > X:
			break
		if useful(ind) > X:
			final = ind
		elif useful(ind) < X:
			initial = ind
	print(ind)


import math
for _ in range(int(input())):
	n = int(input())
	start = int(pow(2.9 * n, 1 / 3))
	end = int(pow(3 * n, 1 / 3))
	for i in range(start, end + 1):
		if i * (i + 1) * (2 * i + 1) / 6 > n:
			print(i - 1)
			break
	else:
		print(end)


T = int(input())
for t in range(T):
	X = int(input())
	(l, r) = (1, X)
	while r - l > 1:
		m = (l + r) // 2
		if m * (m + 1) * (2 * m + 1) // 6 <= X:
			l = m
		else:
			r = m
	print(l)


import sys
lines = [[int(val) for val in line.split()] for line in sys.stdin]
[numinputs, *nums] = lines

def sqsum(n):
	return int(n * (n + 1) * (2 * n + 1) / 6)
for n in nums:
	l = 1
	u = 10000000000000000
	while True:
		m = (l + u) // 2
		sumuptom = sqsum(m)
		if sumuptom == n[0]:
			print(m)
			break
		if sumuptom > n[0] and sqsum(m - 1) <= n[0]:
			print(m - 1)
			break
		elif l > u:
			break
		if sumuptom > n[0]:
			u = m - 1
		elif sumuptom < n[0]:
			l = m + 1


def bs(p, a, b):
	A = a
	B = b
	assert p(a)
	while A != B:
		G = int((A + B) / 2)
		R = p(G)
		if R and (not p(G + 1)):
			return G
		elif R:
			A = int((A + B) / 2)
		else:
			B = int((A + B) / 2)
t = int(input())
m = 10 ** 6
for _ in range(t):
	x = int(input())
	print(bs(lambda g: g * (g + 1) * (2 * g + 1) / 6 <= x, 0, m))


def squaredSum(n):
	return n * (n + 1) * (2 * n + 1) // 6

def binarySearch(arr, el):
	(low, high) = (0, len(arr) - 1)
	while low < high:
		mid = low + (high - low + 1) // 2
		if arr[mid] <= el:
			low = mid
		else:
			high = mid - 1
	return low
limit = 10 ** 16
numbers = []
n = 1
while True:
	total = squaredSum(n)
	numbers.append(total)
	if total >= limit:
		break
	n += 1
t = int(input())
for _ in range(t):
	totalCandies = int(input())
	print(binarySearch(numbers, totalCandies) + 1)


from math import sqrt
from math import pow
T = int(input())
for _ in range(T):
	candies = int(input())
	kids = -1 / 2 + (1 / (pow(3, 1 / 3) * pow(108 * candies + sqrt(3) * sqrt(-1 + 3888 * candies ** 2), 1 / 3)) + pow(108 * candies + sqrt(3) * sqrt(-1 + 3888 * candies ** 2), 1 / 3) / pow(3, 2 / 3)) / 2
	if kids - int(kids) > 0.9999999:
		kids += 1
	print(int(kids))


import fractions, sys
square_pyramidal = lambda n: (2 * n ** 3 + 3 * n ** 2 + n) // 6
T = int(sys.stdin.readline())
for _ in range(T):
	X = int(sys.stdin.readline())
	(L, R) = (1, 1000000)
	while L < R:
		n = (L + R) // 2
		if square_pyramidal(n) < X:
			L = n + 1
		else:
			R = n
	print(L if square_pyramidal(L) <= X else L - 1)


z = int(input())
for case in range(z):
	x = int(input())
	ans = 1
	n = 1
	low = int(x ** (1 / 3))
	high = x
	ans = int((high + low) / 2)
	while high >= low and n != x and (x - n < (ans + 1) ** 3):
		n = ans * (ans + 1) * (2 * ans + 1) / 6
		if n > x:
			high = ans - 1
		if n < x:
			low = ans + 1
		ans = int((high + low) / 2)
	print(int(ans))


T = int(input())
for i in range(0, T):
	N = int(input())
	i = 1
	j = N
	while i <= j:
		mid = int((i + j) / 2)
		temp = (2 * mid ** 3 + 3 * mid ** 2 + mid) / 6
		if temp > N:
			j = mid - 1
		elif temp == N:
			ans = mid
			break
		else:
			ans = mid
			i = mid + 1
	print(ans)


import sys
import math
squares = [(2 * i * i * i + 3 * i * i + i) / 6 for i in range(310722)]
for i in range(int(sys.stdin.readline())):
	X = int(sys.stdin.readline())
	Min = 0
	Max = 310722
	Mid = 0
	condition = True
	while math.floor((Max + Min) / 2) != Mid:
		Mid = math.floor((Max + Min) / 2)
		if X >= squares[Mid]:
			Min = Mid
		else:
			Max = Mid
	print(Mid)


import math

def nth_root(val, n):
	ret = int(val ** (1.0 / n))
	return ret + 1 if (ret + 1) ** n == val else ret

def cal(input):
	k = math.floor(nth_root(input * 3, 3))
	while k * (k + 1) * (2 * k + 1) / 6 > input:
		k -= 1
	return k
n = int(input())
for i in range(0, n):
	num = int(input())
	print(cal(num))


t = int(input())
for i in range(t):
	x = int(input())
	temp = 0
	(left, right, flag) = (1, x, 0)
	while flag == 0 and left <= right:
		temp = (left + right) // 2
		val = temp * (temp + 1) * (2 * temp + 1) // 6
		if val == x:
			flag = 1
		elif val > x:
			right = temp - 1
		else:
			left = temp + 1
	if flag == 1:
		print(temp)
	elif temp * (temp + 1) * (2 * temp + 1) // 6 < x:
		print(temp)
	else:
		print(temp - 1)


from collections import OrderedDict
p = []
s = 0
for i in range(500000):
	s += i * i
	p.append(s)
T = int(input())
xx = OrderedDict()
for i in range(T):
	poop = int(input())
	xx[i] = poop
m1 = min(xx)
x = list(OrderedDict(sorted(xx.items(), key=lambda t: t[1])).keys())
st = int(m1 ** (1 / 3))
for y in x:
	while p[st] <= xx[y]:
		st += 1
	xx[y] = st - 1
for y in xx:
	print(xx[y])


import math

def Find(min, max, X):
	if min == max:
		return min
	n1 = int((min + max) / 2)
	n2 = n1 + 1
	x1 = n1 * (n1 + 1) * (2 * n1 + 1) / 6
	x2 = n2 * (n2 + 1) * (2 * n2 + 1) / 6
	if x1 == X:
		return n1
	elif x2 == X:
		return n2
	elif x1 < X and X < x2:
		return n1
	elif x1 < X:
		return Find(n2, max, X)
	else:
		return Find(min, n1, X)
T = int(input())
while T > 0:
	X = int(input())
	print(Find(1, int(math.sqrt(X)), X))
	T -= 1


def sum_first_n_squares(n):
	return (2 * n * n * n + 3 * n * n + n) // 6

def estimate_n_for_sum_squares(s):
	return int((3 * s) ** (1 / 3))

def find_n_for_sum_squares(s):
	n = estimate_n_for_sum_squares(s)
	ns = sum_first_n_squares(n)
	if ns == s:
		return n
	if ns > s:
		while ns > s:
			ns -= n * n
			n -= 1
		return n
	while ns <= s:
		n += 1
		ns += n * n
	return n - 1

def count_kids(candies):
	return find_n_for_sum_squares(candies)
T = int(input())
for i in range(T):
	candies = int(input())
	print(count_kids(candies))


import sys
square_pyramidal = lambda n: (2 * n ** 3 + 3 * n ** 2 + n) // 6
T = int(sys.stdin.readline())
for _ in range(T):
	X = int(sys.stdin.readline())
	(L, R) = (1, 1000000)
	while L < R:
		n = (L + R) // 2
		if square_pyramidal(n) < X:
			L = n + 1
		else:
			R = n
	print(L if square_pyramidal(L) <= X else L - 1)


import math
T = int(input())
cases = []
for i in range(T):
	X = int(input())
	low = 0
	high = 10000000000000000
	while True:
		mid = (low + high) // 2
		if low == mid or high == mid:
			cases.append(mid)
			break
		sum = mid * (mid + 1) * (2 * mid + 1) // 6
		if sum == X:
			cases.append(mid)
			break
		elif sum > X:
			high = mid
		else:
			low = mid
for case in cases:
	print(case)


def sumSquares(n):
	return n * (n + 1) * (2 * n + 1) // 6
t = int(input())
for _ in range(t):
	x = int(input())
	b = 0
	e = 10 ** 6
	while b + 1 < e:
		s = (b + e) // 2
		if sumSquares(s) <= x:
			b = s
		else:
			e = s
	print(b)


from math import exp, log
t = int(input())
for _ in range(t):
	x = int(input())
	n = int(exp(log(3 * x) / 3))
	s = n * (n + 1) * (2 * n + 1) // 6
	while s > x:
		s = s - n ** 2
		n = n - 1
	while s + (n + 1) ** 2 < x:
		n = n + 1
		s = s + n ** 2
	print(n)


nx = lambda x: n * (n + 1) * (2 * n + 1) // 6
for _ in range(int(input())):
	x = int(input())
	n = int((3 * x) ** (1 / 3))
	while nx(n) < x:
		n += 1
	while nx(n) > x:
		n -= 1
	print(n)


def f(n):
	return n * (n + 1) * (2 * n + 1) // 6
for t in range(int(input())):
	x = int(input())
	(lo, hi) = (0, x + 1)
	while lo < hi:
		mid = lo + (hi - lo) // 2
		if f(mid) <= x:
			lo = mid + 1
		else:
			hi = mid
	print(hi - 1)


from math import sqrt
for _ in range(int(input())):
	x = int(input())
	q = (sqrt(3 * (3888 * x ** 2 - 1)) + 108 * x) ** (1 / 3)
	print(int((q / 3 ** (2 / 3) + 1 / (3 ** (1 / 3) * q) - 0.99999) / 2))


arr = []
for i in range(220000):
	arr.append(((i + 0.5) ** 3 - (i + 0.5) / 4) / 3)

def f(n):
	a = [0, 220000]
	while a[1] - a[0] != 1:
		b = (a[0] + a[1]) // 2
		if n >= arr[b]:
			a[0] = b
		else:
			a[1] = b
	return a[0]
t = int(input().strip())
for i in range(t):
	candies = int(input().strip())
	print(f(candies))


MAXN = 200000

def If_Possible(y, x):
	y = y * (y + 1) * (2 * y + 1)
	y = y // 6
	if y <= x:
		return 1
	else:
		return 0

def solve():
	x = int(input())
	low = 1
	hi = MAXN
	while low < hi:
		mid = (low + hi) // 2
		flag = If_Possible(mid, x)
		if flag == 1:
			low = mid + 1
		else:
			hi = mid
	print(low - 1)

def main():
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


def bs(lo, up, v):
	if lo >= up:
		return lo
	mid = (lo + up + 1) // 2
	mv = mid * (mid + 1) * (2 * mid + 1) // 6
	if mv <= v:
		return bs(mid, up, v)
	else:
		return bs(lo, mid - 1, v)
t = int(input())
for i in range(t):
	x = int(input())
	print(bs(1, x, x))


t = int(input())
for _ in range(t):
	candies_amount = int(input())
	last_child = 0
	formula = lambda x: (2 * x ** 3 + 3 * x ** 2 + x) // 6
	(a, b, c) = (0, 10 ** 6, 0)
	while a < b:
		c = (a + b) // 2
		if formula(c) <= candies_amount:
			a = c + 1
		else:
			b = c
	print(a - 1)


import bisect
n = int(input())
list = []
for i in range(10000):
	if i == 0:
		list.append(1)
	else:
		list.append(list[i - 1] + (i + 1) ** 2)
for i in range(n):
	N = int(input())
	while N > list[-1]:
		list.append(list[-1] + (len(list) + 1) ** 2)
	print(bisect.bisect_right(list, N))


def calc(x):
	return x * (x + 1) * (2 * x + 1) // 6
for _ in range(int(input())):
	X = int(input())
	lo = 1
	hi = 400000
	while lo < hi:
		mid = (lo + hi) // 2
		fx = calc(mid)
		if fx < X:
			lo = mid + 1
		elif fx > X:
			hi = mid - 1
		else:
			break
	while calc(lo + 1) <= X:
		lo += 1
	while calc(lo) > X:
		lo -= 1
	print(lo)


import fileinput

def f(N, a):
	return N * (N + 1) * (2 * N + 1) * 1 / 6 - a

def f_prime(S):
	return S * S + S + 1 / 6

def newt(x, n, plats):
	for i in range(n):
		if f_prime(x) == 0:
			return x
		x = x - f(x, plats) / f_prime(x)
	return x
s = 0
for line in fileinput.input():
	s = s + 1
	if s != 1:
		x = int(line)
		N = 0
		print(int(newt(1, 59, x)))


T = int(input())
for case in range(T):
	X = int(input())
	lo = int((2 * X) ** (1 / 3))
	hi = int((3 * X) ** (1 / 3))
	while lo < hi:
		m = lo + hi + 1 >> 1
		if m * (m + 1) * (2 * m + 1) // 6 <= X:
			lo = m
		else:
			hi = m - 1
	print(lo)


T = int(input().strip())
for i in range(T):
	X = int(input().strip())
	n = int(pow(3 * X, 1 / 3))
	while int(n * (n + 1) * (2 * n + 1) / 6) > X:
		n -= 1
	print(n)


def kios(n):
	return n * (n + 1) * (2 * n + 1) // 6

def blaga(n):
	gus = int((3 * n) ** (1 / 3))
	if kios(gus) <= n:
		return gus
	else:
		return gus - 1
for t in range(int(input())):
	print(blaga(int(input())))


import sys

def solve(s):
	n = int(pow(s * 3, 1 / 3))
	v = n * (n + 1) * (2 * n + 1) // 6
	while v > s:
		v -= n * n
		n -= 1
	return n
t = int(input())
for _ in range(t):
	s = int(input())
	print(solve(s))


def SqSum(n):
	return n * (n + 1) * (2 * n + 1) // 6
t = int(input())
for _ in range(t):
	x = int(input())
	s = 0
	e = 1000000
	while s <= e:
		m = s + (e - s + 1) // 2
		a = SqSum(m)
		b = SqSum(m + 1)
		if a <= x < b:
			print(m)
			break
		elif a < x:
			s = m + 1
		else:
			e = m - 1


def find(n, x):
	return n * (n + 1) * (2 * n + 1) <= 6 * x
t = int(input())
for _ in range(t):
	x = int(input())
	n = int((3 * x) ** (1 / 3))
	for i in range(n, -1, -1):
		if find(i, x):
			print(i)
			break


T = int(input())
for t in range(T):
	X = int(input())
	n = int((3 * X) ** (1 / 3))
	while X < (2 * n ** 3 + 3 * n ** 2 + n) / 6:
		n -= 1
	print(n)


t = int(input())

def squaresums(n):
	return n * (2 * n + 1) * (n + 1) / 6
for _ in range(t):
	n = int(input())
	hi = 10 ** 16
	lo = 0
	mid = (hi + lo) // 2
	while lo + 1 < hi:
		if squaresums(mid) > n:
			hi = mid
		else:
			lo = mid
		mid = (hi + lo) // 2
	print(mid)


def geti(x, start, end):
	while end - start > 1:
		new = (start + end) // 2
		if S[new] < x:
			start = new
		elif S[new] > x:
			end = new
		else:
			return new
	return start
S = []
s = i = 0
limit = 10 ** 16
while s < limit:
	i += 1
	s += i * i
	S.append(s)
T = int(input())
for t in range(T):
	print(geti(int(input()), 0, len(S)) + 1)


T = int(input())
for _ in range(T):
	n_candies = int(input())
	n = int(pow(3 * n_candies, 1 / 3))
	if n * (n + 1) * (2 * n + 1) > 6 * n_candies:
		print(n - 1)
	else:
		print(n)


import bisect
to_give = [0 for i in range(4 * 10 ** 5)]
for i in range(1, len(to_give)):
	to_give[i] = to_give[i - 1] + i ** 2
for _ in range(int(input())):
	print(bisect.bisect_right(to_give, int(input())) - 1)


def main():
	for i in range(int(input())):
		n = int(input())
		k = int(pow(3 * n, 1 / 3))
		if n < k * (k + 1) * (2 * k + 1) // 6:
			k -= 1
		print(k)
main()


def don_candies_fast(x):
	if x == 0:
		return 0
	i_approx = (3 * x) ** (1 / 3) - 1
	if i_approx < 1:
		i = 0
		x0 = x
	else:
		i = int(i_approx) - 1
		x0 = x - i * (i + 1) * (2 * i + 1) // 6
		i += 1
	while x0 >= i * i:
		x0 -= i * i
		i += 1
	if i > 0:
		return i - 1
	else:
		return 0

def do_it():
	Ts = input()
	T = int(Ts)
	for i in range(T):
		xs = input()
		x = int(xs)
		print(don_candies_fast(x))
do_it()


for _ in range(int(input())):
	x = int(input())
	for n in range(int((3 * x) ** (1 / 3)), 10 ** 6):
		if n * (n + 1) * (2 * n + 1) // 6 > x:
			print(n - 1)
			break


import math
list_square_summation = [0]

def findNumberOfChildrenServed(n, start, end):
	if list_square_summation[start] == n:
		return start
	if list_square_summation[end] == n:
		return end
	if list_square_summation[start] < n and list_square_summation[end] > n:
		if end - start == 1:
			return start
		mid = math.ceil((start + end) / 2)
		right = findNumberOfChildrenServed(n, mid, end)
		if right:
			return right
		else:
			return findNumberOfChildrenServed(n, start, mid)
	else:
		return 0

def getNumberOfChildrenServed(n):
	result = findNumberOfChildrenServed(n, 0, len(list_square_summation) - 1)
	if result:
		return result
	for i in range(len(list_square_summation), n + 1):
		sum = int(i * (i + 1) * (2 * i + 1) / 6)
		list_square_summation.append(sum)
		if sum == n:
			return i
		if sum > n:
			return i - 1
	return 0
T = int(input())
while T > 0:
	X = int(input())
	print(getNumberOfChildrenServed(X))
	T -= 1


T = int(input())
for t in range(T):
	x = int(input())
	n = int((3 * x) ** (1.0 / 3)) - 1
	if (n + 1) * (n + 2) * (2 * n + 3) // 6 <= x:
		print(n + 1)
	else:
		print(n)


import math
import sys

def count_candy(total):
	candy_given = 0
	next_child = 0
	while candy_given < total:
		next_child += 1
		candy_given += next_child ** 2
	if candy_given > total:
		next_child -= 1
	return next_child

def compute_candy(total):
	a = 1 / 3
	b = 1 / 2
	c = 1 / 6
	d = -total
	p = -b / (3 * a)
	q = p ** 3 + (b * c - 3 * a * d) / (6 * a ** 2)
	r = c / (3 * a)
	x = (q + (q ** 2 + (r - p ** 2) ** 3) ** (1 / 2)) ** (1 / 3) + (q - (q ** 2 + (r - p ** 2) ** 3) ** (1 / 2)) ** (1 / 3) + p
	print(x, file=sys.stderr)
	return int(math.floor(round(x, 8)))
for _ in range(int(input().strip())):
	print(compute_candy(int(input().strip())))


t = int(input())
for _ in range(t):
	x = int(input())
	i = int((3 * x) ** (1.0 / 3.0))
	while i * (i + 1.0) * (2 * i + 1.0) / 6.0 <= x:
		i += 1
	print(i - 1)


P = []
for i in range(1, 350000):
	P.append(int(i * (i + 1) * (2 * i + 1) / 6))
T = int(input())
for i in range(T):
	X = int(input())
	j = round((3 * X) ** (1 / 3)) - 1
	while j < len(P):
		if P[j] > X:
			break
		j += 1
	print(j)


import math
t = int(input())
while t:
	x = int(input())
	n = 0
	floorN = -1
	while math.floor(n) != floorN:
		floorN = math.floor(n)
		n = n - (n * (n + 1) * (2 * n + 1) / 6 - x) / (n ** 2 + n + 1 / 6)
	sum = 0
	if floorN != 0:
		sum = floorN * (floorN - 1) * (2 * floorN - 1) / 6
		if sum + floorN ** 2 <= x:
			sum += (floorN + 1) ** 2
		else:
			floorN -= 1
		if sum + (floorN + 1) ** 2 <= x:
			floorN += 1
	else:
		floorN = 1
	print(floorN)
	t -= 1


def f(x):
	return x * (x + 1) * (2 * x + 1) // 6
t = int(input())
for _ in range(t):
	x = int(input())
	lo = 1
	hi = int(1000000.0)
	while lo < hi:
		mid = (hi + lo) // 2 + 1
		if f(mid) <= x:
			lo = mid
		else:
			hi = mid - 1
	print(lo)


T = int(input().strip())
for _ in range(T):
	X = int(input().strip())
	(mini, maxi) = (1, 10 ** 8)
	while mini <= maxi:
		cur = (mini + maxi) // 2
		if cur * (cur + 1) * (cur * 2 + 1) // 6 <= X:
			mini = cur + 1
		else:
			maxi = cur - 1
	print(maxi)


def square_sum(x):
	n = int(pow(3 * x - 2, 1 / 3))
	while 2 * n * n * n + 3 * n * n + n > 6 * x:
		n -= 1
	return n
T = int(input())
for t in range(T):
	X = int(input())
	print(square_sum(X))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = int(pow(3 * n, 1 / 3))
	y = int(l * (l + 1) * (2 * l + 1) / 6)
	if y > n:
		print(l - 1)
	else:
		print(l)


def answer(X):
	r = pow(3 * X, 1 / 3)
	while True:
		nr = r - (r * (r + 1) * (2 * r + 1) - 6 * X) / (6 * r * (r + 1) + 1)
		if abs(r - nr) < 1e-06:
			return int(nr)
		r = nr
a = []
for _ in range(int(input())):
	a.append(answer(int(input())))
for i in range(len(a)):
	print(a[i])


import math

def sumSquares(n):
	return n * (n + 1) * (2 * n + 1) // 6

def computeNChildren(X):
	hi = math.floor((3 * X) ** (1.0 / 3))
	lo = math.ceil(X ** (1.0 / 3))
	while hi - lo > 1:
		mid = int((lo + hi) / 2)
		if sumSquares(mid) < X:
			lo = mid
		elif sumSquares(mid) > X:
			hi = mid
		else:
			return mid
	if sumSquares(hi) <= X:
		return hi
	return hi - 1
line = input()
ctests = int(line)
for itest in range(ctests):
	line = input()
	X = int(line)
	print(computeNChildren(X))


def sqsum(x):
	return x * (x + 1) * (2 * x + 1) // 6
num_cases = int(input())
for _ in range(num_cases):
	x = int(input())
	lo = 1
	hi = x
	while lo + 1 < hi:
		mid = (lo + hi) // 2
		if x >= sqsum(mid):
			lo = mid
		else:
			hi = mid
	print(lo)


import sys

def s2(n):
	return n * (n + 1) * (2 * n + 1) // 6
for _ in range(int(input())):
	x = int(input())
	n = int(pow(3 * x, 0.33333)) - 1
	assert s2(n) <= x
	while s2(n + 1) <= x:
		n += 1
	print(n)


T = int(input())
for _ in range(T):
	flag = True
	tot = int(input())
	testcount = int((3 * tot) ** 0.33333) + 100
	while flag:
		pyram = testcount * (testcount + 1) * (2 * testcount + 1) / 6
		if tot >= pyram:
			flag = False
			print(testcount)
		else:
			testcount = testcount - 1


import math
t = int(input().strip())
max = 10 ** 16

def sum_of_squares(n):
	return n * (n + 1) * (2 * n + 1) / 6
for a0 in range(t):
	n = int(input().strip())
	hi = max
	lo = 0
	while True:
		x = math.floor((hi + lo) / 2)
		if sum_of_squares(x) > n:
			hi = x
		elif sum_of_squares(x) < n:
			lo = x
		else:
			print(x)
			break
		if hi - lo <= 1:
			print(lo)
			break


from math import sqrt
from fractions import gcd

def find(i):
	l = 0
	r = 310725
	m = 0
	while l < r:
		m = (l + r + 1) // 2
		if a[m] == i:
			return m
		if a[m] > i:
			r = m - 1
		else:
			l = m
	return l
a = [0] * 310725
t = 0
for i in range(1, 310725):
	a[i] = a[i - 1] + i ** 2
t = int(input())
while t != 0:
	t -= 1
	p = int(input())
	s = find(p)
	print(s)


T = int(input())
for _ in range(T):
	X = int(input())
	s = int((3 * X) ** (1 / 3)) - 1
	while True:
		N = s + 1
		if N * (N + 1) * (2 * N + 1) / 6 > X:
			print(s)
			break
		else:
			s += 1


T = int(input().strip())
for _ in range(T):
	X = int(input().strip())
	bound = int(pow(3 * X, 1 / 3))
	candies = bound * (bound + 1) * (2 * bound + 1) // 6
	count = bound
	while candies > X:
		candies -= count ** 2
		count -= 1
	print(count)


import sys
import bisect
nums = list(map(lambda x: x.strip(), sys.stdin.readlines()))
nums.pop(0)
arr = [i * (i + 1) * (2 * i + 1) // 6 for i in range(200000)]
for n in nums:
	num = int(n)
	ind = bisect.bisect(arr, num)
	ind = ind - 1
	if ind <= -1:
		ind = 0
	print(ind)


import math

def f(n):
	return n * (n + 1) * (2 * n + 1) / 6
bits = []
for i in range(20):
	bits.append(int(2 ** i))
debug = True
N = int(input())
for _ in range(N):
	x = int(input())
	a = 0
	for i in range(len(bits) - 1, -1, -1):
		j = bits[i]
		if f(a + j) <= x:
			a += j
	print(a)


def sum_n_squared(n):
	return n * (n + 1) * (2 * n + 1) // 6
num_tests = int(input())
for i in range(num_tests):
	candies = int(input())
	max_children = 1
	while sum_n_squared(max_children) <= candies:
		max_children *= 2
	(l, r) = (max_children // 2, max_children)
	while l <= r:
		mid = (l + r) // 2
		if sum_n_squared(mid) <= candies:
			l = mid + 1
		else:
			r = mid - 1
	children = max(l, r)
	if sum_n_squared(children) <= candies:
		print(children)
	else:
		print(children - 1)


def sum_i2(N):
	return (2 * N ** 3 + 3 * N ** 2 + N) // 6

def brute(N):
	return sum((x ** 2 for x in range(N + 1)))

def binary_search(x):
	left = 0
	fl = 0
	right = int(350000.0)
	fr = sum_i2(right)
	while right - left > 1:
		middle = (right + left) // 2
		f = sum_i2(middle)
		if f > x:
			(right, fr) = (middle, f)
		else:
			(left, fl) = (middle, f)
	return left
t = int(input())
for _ in range(t):
	n = int(input())
	print(binary_search(n))


for _ in range(int(input())):
	x = int(input())
	n = int((3 * x) ** 0.3333333333333333)
	while n > 0:
		if n * (n + 1) * (2 * n + 1) / 6 <= x:
			print(n)
			break
		n -= 1


def answer(X):
	r = pow(3 * X, 1 / 3.0)
	while True:
		nr = r - (r * (r + 1) * (2 * r + 1) - 6 * X) / (6 * r * (r + 1) + 1)
		if abs(r - nr) < 1e-06:
			return int(nr)
		r = nr
t = int(input())
for i in range(t):
	print(answer(int(input())))


test_case = int(input())
for i in range(test_case):
	x = int(input())
	y = int((x * 3) ** (1.0 / 3.0))
	ans = x - y * (y + 1) * (2 * y + 1) / 6
	if ans >= 0:
		print(y)
	else:
		print(int(y - 1))


for l in range(int(input())):
	n = int(input())
	x = int(pow(3 * n, 1 / 3))
	for j in range(500):
		f = 2 * pow(x, 3) + 3 * pow(x, 2) + x - 6 * n
		d = 6 * pow(x, 2) + 6 * x + 1
		y = x - f / d
	print(int(y))


from math import pow

def sum_eq(x):
	return x * (x + 1) * (2 * x + 1) // 6

def res(x):
	return int(pow(x * 3, 1 / 3))
for _ in range(int(input())):
	x = int(input())
	r = res(x)
	while sum_eq(r) > x:
		r -= 1
	print(r)


import bisect
N_max = 4 * 10 ** 5
S = [0] * (N_max + 1)
for i in range(1, N_max + 1):
	S[i] = S[i - 1] + i ** 2
T = int(input())
for _ in range(T):
	X = int(input())
	print(bisect.bisect(S, X) - 1)