There are Infinite People Standing in a row, indexed from 1.
A person having index 'i' has strength of (i*i).
You have Strength 'P'. You need to tell what is the maximum number of People You can Kill With your Strength P.
You can only Kill a person with strength 'X' if P >= 'X'  and after killing him, Your Strength decreases by 'X'. 
 
Example 1:
Input:
N = 14
Output: 3
Explanation:
The strengths of people is 1, 4, 9, 16, .... 
and so on. WE can kill the first 3 person , 
after which our Power becomes 0 and we cant 
kill anyone else. So answer is 3
 
Example 2:
Input:
N = 10
Output: 2
Your Task:  
You don't need to read input or print anything. Your task is to complete the function killinSpree() which takes the integer N as input parameters and returns the maximum Number of People You can kill.
Expected Time Complexity: O(log(n))
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ T ≤ 10^{3}
1 ≤ N ≤ 10^{12}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Divide and conquer

Mathematics

Starter code: #User function Template for python3



class Solution:

    def killinSpree (self, n):

        # code here





Solutions:
class Solution:

	def killinSpree(self, n):
		p = lambda n: n * (n + 1) * (2 * n + 1) // 6
		(lo, hi) = (0, n + 1)
		while lo < hi:
			mi = lo + (hi - lo) // 2
			if p(mi) > n:
				hi = mi
			else:
				lo = mi + 1
		return lo - 1


class Solution:

	def killinSpree(self, n):

		def _solve(x):
			return x * (x + 1) * (2 * x + 1) // 6
		(L, R) = (0, 20000)
		while L < R:
			m = (L + R) // 2
			if _solve(m) <= n:
				L = m + 1
			else:
				R = m
		return L - 1


class Solution:

	def killinSpree(self, n):
		(L, R) = (1, 10 ** 9)
		ans = None
		while L <= R:
			M = L + (R - L) // 2
			if M * (M + 1) * (2 * M + 1) // 6 <= n:
				ans = M
				L = M + 1
			else:
				R = M - 1
		return ans


class Solution:

	def valid(self, k, n):
		return k * (k + 1) * (2 * k + 1) // 6 <= n

	def killinSpree(self, n):
		lower = 1
		upper = n
		while lower < upper - 1:
			candidate = (upper + lower) // 2
			if self.valid(candidate, n):
				lower = candidate
			else:
				upper = candidate
		return lower


class Solution:

	def killinSpree(self, n):
		low = 1
		high = 1000000
		count = 0
		while low <= high:
			mid = low + (high - low) // 2
			val = mid * (mid + 1) * (2 * mid + 1) // 6
			if val <= n:
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return ans


class Solution:

	def killinSpree(self, n):
		low = 0
		high = 1000000000000000
		while low <= high:
			mid = low + (high - low) // 2
			value = mid * (mid + 1) * (2 * mid + 1) // 6
			if value <= n:
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return ans


class Solution:

	def killinSpree(self, n):
		l = 1
		h = 100000000.0
		a = 0
		while l <= h:
			m = l + (h - l) // 2
			r = m * (m + 1) * (2 * m + 1) // 6
			if n < r:
				h = m - 1
			else:
				a = m
				l = m + 1
		return int(a)


arr = [0]
import bisect

class Solution:

	def killinSpree(self, n):
		self.helper(n)
		return bisect.bisect(arr, n) - 1

	def helper(self, n):
		i = len(arr)
		summa = arr[-1]
		while summa < n:
			summa += i ** 2
			i += 1
			arr.append(summa)
		return


class Solution:

	def killinSpree(self, n):
		start = 1
		end = 10 ** 6
		res = 0
		while start <= end:
			mid = start + (end - start) // 2
			value = mid * (mid + 1) * (2 * mid + 1) // 6
			if value == n:
				res = mid
				break
			elif value < n:
				res = mid
				start = mid + 1
			else:
				end = mid - 1
		return res


def totalStrengthReq(mid):
	return mid * (mid + 1) * (2 * mid + 1) // 6

class Solution:

	def killinSpree(self, n):
		(lo, hi) = (1, n)
		ans = -1
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			x = totalStrengthReq(mid)
			if n >= x:
				ans = mid
				lo = mid + 1
			else:
				hi = mid - 1
		return ans


def strength(mid):
	return mid * (mid + 1) * (2 * mid + 1) / 6

class Solution:

	def killinSpree(self, n):
		(lo, hi) = (1, n)
		ans = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			X = strength(mid)
			if n >= X:
				ans = mid
				lo = mid + 1
			else:
				hi = mid - 1
		return ans


class Solution:

	def binarysearch(self, l, r, n):
		if l <= r:
			mid = (l + r) // 2
			s = mid * (mid + 1) * (2 * mid + 1) // 6
			if s <= n:
				return self.binarysearch(mid + 1, r, n)
			else:
				return self.binarysearch(l, mid - 1, n)
		return r

	def killinSpree(self, n):
		return self.binarysearch(0, 1000000, n)


class Solution:

	def killinSpree(self, n):
		l = 1
		r = n
		res = 0
		while l <= r:
			mid = (l + r) // 2
			s = mid * (mid + 1) * (2 * mid + 1) // 6
			if s <= n:
				res = mid
				l = mid + 1
			else:
				r = mid - 1
		return res


def s(i):
	return i * (i + 1) * (2 * i + 1) // 6

class Solution:

	def killinSpree(self, n):
		(st, en) = (0, int(n ** 0.5) + 1)
		ans = 0
		while st <= en:
			mid = (st + en) // 2
			c = s(mid)
			if c == n:
				return mid
			elif c > n:
				en = mid - 1
			else:
				st = mid + 1
				ans = mid
		return ans


class Solution:

	def Formula(self, n):
		return n * (n + 1) * (2 * n + 1) // 6

	def killinSpree(self, n):
		l = 1
		h = 10000000.0
		ans = 0
		mid = l + (h - l) // 2
		if n == 0:
			return 0
		while l <= h:
			mid = l + (h - l) // 2
			if int(self.Formula(mid)) <= n:
				ans = mid
				l = mid + 1
			else:
				h = mid - 1
		return int(ans)


MAX = int(1000000000000.0)
dp = []

def compute():
	i = 1
	while i * i <= MAX:
		dp.append(i * i)
		i += 1

def bs(key):
	l = 0
	r = len(dp) - 1
	ans = 0
	while l <= r:
		mid = l + (r - l) >> 1
		if dp[mid] == key:
			return mid
		if dp[mid] < key:
			l = mid + 1
		else:
			r = mid - 1
	return ans

class Solution:

	def killinSpree(self, n):

		def sumt(h):
			return h * (h + 1) * (2 * h + 1) / 6
		h = 1
		AC = 0
		sta = 0
		endd = 144225
		while sta <= endd:
			midd = (sta + endd) // 2
			if sumt(midd) <= n:
				AC = max(AC, midd)
				sta = midd + 1
			else:
				endd = midd - 1
		return AC


class Solution:

	def killinSpree(self, n):
		low = 0
		up = n
		ans = 0
		while low <= up:
			mid = (low + up) // 2
			power = mid * (mid + 1) * (2 * mid + 1)
			if power <= n * 6:
				low = mid + 1
				ans = max(ans, mid)
			else:
				up = mid - 1
		return ans


class Solution:

	def killinSpree(self, n):
		(low, high) = (1, 2 ** 32 - 1)
		while low <= high:
			mid = (high + low) // 2
			temp = mid * (mid + 1) * (2 * mid + 1) // 6
			if temp > n:
				high = mid - 1
			elif temp == n:
				return mid
			else:
				low = mid + 1
		return low - 1


import math

class Solution:

	def killinSpree(self, n):

		def sum(n):
			a = n * (n + 1) * (2 * n + 1) / 6
			return a
		(low, high) = (0, n + 1)
		while low < high:
			mid = low + (high - low) // 2
			if sum(mid) > n:
				high = mid
			else:
				low = mid + 1
		return low - 1


class Solution:

	def ss(self, n):
		return n * (n + 1) * (2 * n + 1) // 6

	def killinSpree(self, n):
		(l, r) = (1, n)
		while l != r:
			mid = (l + r) // 2
			if mid == l:
				return l if self.ss(r) > n else r
			if self.ss(mid) > n:
				r = mid
			elif self.ss(mid) < n:
				l = mid
			else:
				return mid
		return l


class Solution:

	def killinSpree(self, n):
		cnt = -1
		start = 0
		end = n
		while start <= end:
			mid = (start + end) // 2
			midSquareSum = int(mid * (mid + 1) * (2 * mid + 1) / 6)
			if midSquareSum <= n:
				cnt = mid
				start = mid + 1
			else:
				end = mid - 1
		return cnt


class Solution:

	def killinSpree(self, n):
		s = 1
		e = n
		ans = 0
		while s <= e:
			m = s + (e - s) // 2
			x = m * (m + 1) * (2 * m + 1) // 6
			if x <= n:
				ans = m
				s = m + 1
			else:
				e = m - 1
		return ans


class Solution:

	def killinSpree(self, n):
		(l, h) = (0, n)
		while l <= h:
			mid = (l + h) // 2
			if 2 * mid * mid * mid + 3 * mid * mid + mid <= 6 * n:
				l = mid + 1
			else:
				h = mid - 1
		return l - 1


class Solution:

	def killinSpree(self, n):

		def add(x):
			return x * (x + 1) * (2 * x + 1) // 6
		if n == 0:
			return 0
		low = 1
		high = 10000000.0
		ans = 0
		while low <= high:
			mid = low + (high - low) // 2
			sum = add(mid)
			if sum <= n:
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return int(ans)


class Solution:

	def killinSpree(self, n):
		l = 0
		r = n
		while l <= r:
			m = l + r >> 1
			if m * (m + 1) * (2 * m + 1) <= 6 * n:
				l = m + 1
			else:
				r = m - 1
		return l - 1


class Solution:

	def sum_n2(self, n):
		return n * (n + 1) * (2 * n + 1) / 6

	def killinSpree(self, P):
		i = 1
		count = 0
		l = 1
		r = P
		while l <= r:
			i = (l + r) // 2
			sum = self.sum_n2(i)
			if P == sum:
				return i
			if P > sum:
				l = i + 1
			if P < sum:
				r = i - 1
		return l - 1


class Solution:

	def killinSpree(self, n):
		low = 1
		high = 1000000
		mid = 0
		while low <= high:
			mid = low + (high - low) // 2
			f = mid * (mid + 1) * (2 * mid + 1) / 6
			if n == f:
				return mid
			elif n < f:
				high = mid - 1
			else:
				low = mid + 1
		return low - 1


class Solution:

	def killinSpree(self, n):

		def sumt(h):
			return h * (h + 1) * (2 * h + 1) / 6
		h = 1
		AC = 0
		sta = 0
		endd = 144225
		while sta <= endd:
			midd = (sta + endd) // 2
			if sumt(midd) <= n:
				AC = max(AC, midd)
				sta = midd + 1
			else:
				endd = midd - 1
		return AC


class Solution:

	def killinSpree(self, n):
		i = 1
		j = n
		while i < j:
			mid = i + j + 1 >> 1
			ans = (mid + 1) * (mid * 2 + 1) * mid // 6
			if ans > n:
				j = mid - 1
			else:
				i = mid
		return i


class Solution:

	def killinSpree(self, n):
		(i, j) = (0, n)
		while i <= j:
			k = (i + j) // 2
			if 2 * k * k * k + 3 * k * k + k <= 6 * n:
				i = k + 1
			else:
				j = k - 1
		return i - 1


class Solution:

	def killinSpree(self, n):
		lo = 1
		hi = 1000000
		count = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			val = mid * (mid + 1) * (2 * mid + 1) // 6
			if val <= n:
				ans = mid
				lo = mid + 1
			else:
				hi = mid - 1
		return ans


class Solution:

	def killinSpree(self, n):

		def vaild(target, n):
			temp = target * (target + 1) * (2 * target + 1) // 6
			return n >= temp
		start = 1
		end = n
		ans = -1
		while start <= end:
			mid = (start + end) // 2
			if vaild(mid, n):
				ans = mid
				start = mid + 1
			else:
				end = mid - 1
		return ans


class Solution:

	def killinSpree(self, n):
		v = lambda n: n * (n + 1) * (2 * n + 1) // 6
		(lower, upper) = (0, n + 1)
		while lower < upper:
			mid = lower + (upper - lower) // 2
			if v(mid) > n:
				upper = mid
			else:
				lower = mid + 1
		return lower - 1


class Solution:

	def killinSpree(self, n):
		l = 1
		h = int(n ** (1 / 2))
		ans = 1
		while l <= h:
			m = int((l + h) / 2)
			t = m * (m + 1) * (2 * m + 1) / 6
			if n - t >= 0:
				ans = m
				l = m + 1
			else:
				h = m - 1
		return ans


class Solution:

	def killinSpree(self, n):
		import math
		(start, end) = (1, math.ceil((3 * n) ** (1 / 3)))
		while start <= end:
			mid = (start + end) // 2
			summation = mid * (mid + 1) * (2 * mid + 1) // 6
			if summation == n:
				return mid
			elif summation < n:
				start = mid + 1
			else:
				end = mid - 1
		return end


class Solution:

	def killinSpree(self, n):
		start = 0
		end = 100000.0
		mid = start + (end - start) // 2
		ans = 0
		while start <= end:
			condition = mid * (mid + 1) * (2 * mid + 1) // 6
			if n >= condition:
				ans = mid
				start = mid + 1
			else:
				end = mid - 1
			mid = start + (end - start) // 2
		return int(ans)


import bisect

class Solution:

	def killinSpree(self, n):
		start = 0
		end = 100000.0
		mid = start + (end - start) // 2
		ans = 0
		while start <= end:
			a = mid
			condition = a * (a + 1) * (2 * a + 1) // 6
			if n >= condition:
				ans = mid
				start = mid + 1
			elif n < condition:
				end = mid - 1
			mid = start + (end - start) // 2
		return int(ans)


class Solution:

	def killinSpree(self, n):
		l = 0
		h = n
		while l <= h:
			m = (l + h) // 2
			if m * (m + 1) * (2 * m + 1) // 6 > n:
				h = m - 1
			else:
				l = m + 1
		for i in range(m - 2, m + 2):
			if i * (i + 1) * (2 * i + 1) // 6 > n:
				return i - 1


class Solution:

	def killinSpree(self, n):
		hi = int((6 * n) ** (1 / 3))
		lo = 1
		while lo <= hi:
			mid = (lo + hi) // 2
			res = mid * (mid + 1) * (2 * mid + 1)
			if res <= 6 * n and (mid + 1) * (mid + 2) * (2 * mid + 3) > 6 * n:
				return mid
			elif res > 6 * n:
				hi = mid - 1
			else:
				lo = mid + 1
		return 0
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		N = int(input())
		ans = ob.killinSpree(N)
		print(ans)


class Solution:

	def killinSpree(self, p):
		ans = 0
		l = 0
		r = p
		while l <= r:
			mid = (l + r) // 2
			cond = p - (mid - 1) * mid * (2 * mid - 1) / 6
			if cond >= mid ** 2:
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		N = int(input())
		ans = ob.killinSpree(N)
		print(ans)


import math

class Solution:

	def killinSpree(self, n):
		low = 0
		high = math.floor(math.sqrt(n))
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			value = mid * (mid + 1) * (2 * mid + 1) / 6
			if value <= n:
				low = mid + 1
				ans = mid
			else:
				high = mid - 1
		return ans
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		N = int(input())
		ans = ob.killinSpree(N)
		print(ans)


class Solution:

	def killinSpree(self, n):

		def squareSum(x):
			return x * (x + 1) * (2 * x + 1) // 6
		low = 1
		high = 1000000.0
		result = -1
		while low <= high:
			mid = int((low + high) // 2)
			if squareSum(mid) > n:
				high = mid - 1
			elif squareSum(mid) < n:
				result = mid
				low = mid + 1
			else:
				return mid
		return result


import math

class Solution:

	def killinSpree(self, n):
		low = 1
		high = int(math.sqrt(n))
		sum_till_here = 0
		while low <= high:
			mid = int(low + (high - low) / 2)
			sum_till_here = int(mid * (mid + 1) * (2 * mid + 1) / 6)
			if sum_till_here == n:
				return mid
			elif sum_till_here > n:
				high = mid - 1
			else:
				result = mid
				low = mid + 1
		return result


class Solution:

	def killinSpree(self, n):

		def solve(x):
			return x * (x + 1) * (2 * x + 1) // 6
		if n == 0:
			return 0
		start = 1
		end = 1000000.0
		ans = 0
		while start <= end:
			mid = start + (end - start) // 2
			summ = solve(mid)
			if summ <= n:
				ans = mid
				start = mid + 1
			else:
				end = mid - 1
		return int(ans)


import math

class Solution:

	def killinSpree(self, n):
		s = 1
		e = int(math.sqrt(n) + 1)
		ans = 0
		while s <= e:
			m = s + (e - s) // 2
			su = m * (m + 1) * (2 * m + 1) // 6
			if su <= n:
				ans = m
				s = m + 1
			else:
				e = m - 1
		return ans


class Solution:

	def killinSpree(self, n):

		def sumt(h):
			return h * (h + 1) * (2 * h + 1) / 6
		h = 1
		AC = 0
		s = 0
		e = 144225
		while s <= e:
			midd = (s + e) // 2
			if sumt(midd) <= n:
				AC = max(AC, midd)
				s = midd + 1
			else:
				e = midd - 1
		return AC


class Solution:

	def killinSpree(self, n):
		low = 1
		high = 2 * n
		output = 0
		total = 0
		while low <= high:
			mid = (low + high) // 2
			total = mid * (mid + 1) * (2 * mid + 1) // 6
			if total <= n:
				output = mid
				low = mid + 1
			else:
				high = mid - 1
		return output


class Solution:

	def killinSpree(self, n):
		low = 1
		high = 100000
		ans = 0
		while low <= high:
			mid = low + (high - low) // 2
			x = mid * (mid + 1) * (2 * mid + 1) // 6
			if x <= n:
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return ans


import math

class Solution:

	def killinSpree(self, n):
		l = 1
		h = int(math.sqrt(n)) + 1
		ans = 0
		while l <= h:
			m = (l + h) // 2
			k = int(m * (m + 1) * (2 * m + 1) / 6)
			if k <= n:
				if m > ans:
					ans = m
				l = m + 1
			else:
				h = m - 1
		return ans


class Solution:

	def killinSpree(self, n):
		low = 1
		high = n + 1
		while low < high:
			mid = (low + high + 1) // 2
			if n >= mid * (mid + 1) * (2 * mid + 1) // 6:
				low = mid
			else:
				high = mid - 1
		return low


import math

class Solution:

	def killinSpree(self, n):
		low = 1
		high = math.ceil(math.sqrt(n))
		ans = 1
		while low <= high:
			mid = (low + high) // 2
			power = mid * (mid + 1) * (2 * mid + 1) // 6
			if power == n:
				return mid
			elif power > n:
				high = mid - 1
			else:
				ans = mid
				low = mid + 1
		return ans


import math

class Solution:

	def killinSpree(self, n):
		(l, r) = (1, math.ceil(math.sqrt(n)))
		res = 0
		while l <= r:
			mid = (l + r) // 2
			z = mid * (mid + 1) * (2 * mid + 1) // 6
			if n == z:
				return mid
			elif z < n:
				res = mid
				l = mid + 1
			else:
				r = mid - 1
		return res


import math as m

class Solution:

	def killinSpree(self, n):
		(lo, ans) = (0, 0)
		hi = int(m.sqrt(n))
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			val = mid * (mid + 1) * (2 * mid + 1) // 6
			if val <= n:
				ans = mid
				lo = mid + 1
			else:
				hi = mid - 1
		return ans


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

class Solution:

	def killinSpree(self, n):
		bot = 1
		top = n
		result = 0
		while bot <= top:
			mid = (bot + top) // 2
			s = getSum(mid)
			if s <= n:
				result = mid
				bot = mid + 1
			else:
				top = mid - 1
		return result


class Solution:

	def killinSpree(self, n):
		l = 1
		r = 10 ** 12
		ans = -1
		while r >= l:
			mid = (l + r) // 2
			res = mid * (mid + 1) * (2 * mid + 1) // 6
			if res <= n:
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans


class Solution:

	def killinSpree(self, n):
		if n == 1:
			return 1

		def findSum(k):
			return k * (k + 1) * (2 * k + 1) // 6
		res = 0
		start = 1
		end = n
		while start < end:
			mid = (start + end) // 2
			sm = findSum(mid)
			if sm == mid:
				return mid
			if sm > n:
				end = mid
			else:
				res = mid
				start = mid + 1
		return res


class Solution:

	def killinSpree(self, n):
		l = 1
		h = n
		while l <= h:
			m = l + h >> 1
			if m * (m + 1) * (2 * m + 1) // 6 == n:
				return m
			elif m * (m + 1) * (2 * m + 1) // 6 > n:
				h = m - 1
			else:
				l = m + 1
		return h


from math import *

class Solution:

	def killinSpree(self, n):
		l = 1
		h = int(sqrt(n))
		while l <= h:
			m = (l + h) // 2
			if m * (m + 1) * (2 * m + 1) // 6 == n:
				return m
			elif m * (m + 1) * (2 * m + 1) // 6 > n:
				h = m - 1
			else:
				l = m + 1
		return h


class Solution:

	def killinSpree(self, n):
		s = 1
		e = int(n ** 0.5)
		while s <= e:
			mid = s + e >> 1
			p = mid * (mid + 1) * (2 * mid + 1) // 6
			if p > n:
				e = mid - 1
			else:
				s = mid + 1
		return e


class Solution:

	def killinSpree(self, n):
		(i, j) = (1, 10 ** 12)
		count = -1
		while j >= i:
			mid = (i + j) // 2
			if mid * (mid + 1) * (2 * mid + 1) // 6 <= n:
				count = mid
				i = mid + 1
			else:
				j = mid - 1
		return count


class Solution:

	def killinSpree(self, n):
		s = 0
		ans = 0
		i = 1
		while n > 0:
			s = i * (i + 1) * (2 * i + 1) // 6
			if n > s:
				i = 2 * i
			elif n == s:
				ans = i
				break
			else:
				low = i // 2
				high = i
				while low <= high:
					mid = (low + high) // 2
					s = mid * (mid + 1) * (2 * mid + 1) // 6
					if s > n:
						high = mid - 1
					elif s == n:
						ans = mid
						break
					else:
						nex = (mid + 1) * (mid + 1 + 1) * (2 * (mid + 1) + 1) // 6
						if nex > n:
							ans = mid
							break
						low = mid + 1
				break
		return ans


import math

class Solution:

	def killinSpree(self, n):
		l = 1
		r = int(math.sqrt(n))
		ans = 0
		while l <= r:
			mid = l + (r - l) // 2
			cal = mid * (mid + 1) * (2 * mid + 1) // 6
			if cal <= n:
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans