Read problems statements in Mandarin Chinese , Russian and Vietnamese as well. 

Chef belongs to a very rich family which owns many gold mines. Today, he brought N gold coins and decided to form a triangle using these coins. Isn't it strange?

Chef has a unusual way of forming a triangle using gold coins, which is described as follows:
He puts 1 coin in the 1^{st} row.
then puts 2 coins in the 2^{nd} row.
then puts 3 coins in the 3^{rd} row.
and so on as shown in the given figure.
Chef is interested in forming a triangle with maximum possible height using at most N coins. Can you tell him the maximum possible height of the triangle?

------ Input ------ 

The first line of input contains a single integer T denoting the number of test cases. 
The first and the only line of each test case contains an integer N denoting the number of gold coins Chef has.

------ Output ------ 

For each test case, output a single line containing an integer corresponding to the maximum possible height of the triangle that Chef can get.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{9}$

------ Subtasks ------ 

$Subtask 1 (48 points) : 1 ≤ N ≤ 10^{5}$
$Subtask 2 (52 points) : 1 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
3
5
7
----- Sample Output 1 ------ 
2
2
3
----- explanation 1 ------ 
Test 1: Chef can't form a triangle with height > 2 as it requires atleast 6 gold coins.
Test 2: Chef can't form a triangle with height > 2 as it requires atleast 6 gold coins.
Test 3: Chef can't form a triangle with height > 3 as it requires atleast 10 gold coins.

Difficulty: EASY
Tags: Mathematics

Sorting

Implementation

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	n = n * 2
	h = 0
	while True:
		h += 1
		x = h * (h + 1)
		if x > n:
			break
	print(h - 1)


t = int(input())
for _ in range(t):
	i = 1
	c = 0
	n = int(input())
	for i in range(1, n + 1):
		i = i * (i + 1) // 2
		if i > n:
			break
		else:
			c += 1
	print(c)


T = int(input())
for j in range(T):
	a = int(input())
	c = 0
	for i in range(1, a + 1):
		i = i * (i + 1) / 2
		if i > a:
			break
		else:
			c = c + 1
	print(c)


T = int(input())
for i in range(T):
	N = int(input())
	count = 0
	for i in range(1, N + 1):
		if N < i:
			break
		N -= i
		count += 1
	print(count)


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


for _ in range(int(input())):
	n = int(input())
	lines = 0
	while True:
		if lines * (lines + 1) / 2 <= n:
			lines += 1
		else:
			break
	print(lines - 1)


def solve(n):
	left = 0
	right = n
	mid = (left + right) // 2
	while not ((mid + 1) * mid / 2 <= n and (mid + 2) * (mid + 1) / 2 > n):
		mid = (left + right) // 2
		if (mid + 2) * (mid + 1) / 2 <= n and right >= left:
			left = mid + 1
		elif (mid + 1) * mid / 2 > n and right >= left:
			right = mid - 1
	return mid
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


def sq_root(val):
	n = val
	m = 1
	e = 1e-06
	while n - m > e:
		n = (n + m) / 2
		m = val / n
	return n

def find(ip_num):
	val = 1 + 8 * ip_num
	maxHeight = int((-1 + sq_root(val)) / 2)
	print(maxHeight)
for i in range(int(input())):
	ip_num = int(input())
	find(ip_num)


def main(n):
	(result, i) = (0, 1)
	while n > 0 and n >= i:
		n -= i
		result = i
		i += 1
	print(result)
for i in range(int(input())):
	N = int(input())
	main(N)


for x in range(int(input())):
	n = int(input())
	i = 1
	c = 0
	while i <= n:
		n = n - i
		if n >= 0:
			c = c + 1
		i = i + 1
	print(c)


for _ in range(int(input())):
	sum_gold = int(input())
	i = 0
	while sum_gold >= i:
		i += 1
		sum_gold -= i
	print(i)


t = int(input())
arr = []
for i in range(t):
	arr.append(int(input()))
res = [0 for i in range(len(arr))]
for i in range(len(arr)):
	row = 1
	while arr[i] - row >= 0:
		arr[i] -= row
		row += 1
	print(row - 1)


for _ in range(int(input())):
	n = int(input())
	height = 0
	coins = 1
	while True:
		if n - coins >= 0:
			n -= coins
			height += 1
			coins += 1
		else:
			break
	print(height)


for i in range(int(input())):
	n = int(input())
	k = 1
	j = 1
	c = 0
	while k <= n:
		j += 1
		k += j
		c += 1
	print(c)


for _ in range(int(input())):
	x = int(input())
	count = 1
	height = 0
	a = 1
	while a > 0:
		if x - count >= 0:
			x = x - count
			count += 1
			height += 1
		else:
			break
	print(height)


t = int(input())
for i in range(t):
	x = int(input())
	c = 0
	i = 1
	for i in range(1, x + 1):
		i = i * (i + 1) // 2
		if i > x:
			break
		else:
			c = c + 1
	print(c)


for t in range(int(input())):
	n = int(input())
	i = 1
	h = 0
	while n >= i:
		n = n - i
		h = h + 1
		i = i + 1
	print(h)


array = []

def max_triangle_height(N):
	coins = 0
	row = 1
	while coins + row <= N:
		coins += row
		row += 1
	return array.append(row - 1)
T = int(input())
if 1 <= T <= 100:
	for N in range(T):
		N = int(input())
		max_triangle_height(N)
for i in array:
	print(i)
	i = i + 1


from math import *
testcase_no = int(input())
for testcases in range(testcase_no):
	n = int(input())
	ans = floor((-1 + sqrt(1 + 8 * n)) / 2)
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	c = 0
	for i in range(1, n + 1):
		n = n - i
		if n < 0:
			break
		else:
			c = c + 1
	print(c)


for i in range(int(input())):
	n = int(input())
	for i in range(1, n + 1):
		if i * (i + 1) // 2 == n:
			print(i)
			break
		elif i * (i + 1) // 2 > n:
			print(i - 1)
			break


t = int(input())
while t > 0:
	n = int(input())
	height = 0
	total_coins = 0
	while total_coins <= n:
		height += 1
		total_coins += height
	print(height - 1)
	t -= 1


for i in range(int(input())):
	x = int(input())
	prev = 0
	n = 1
	count = 0
	sum = 0
	while sum < x:
		count += 1
		n += 1
		sum += n
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	s = 0
	while True:
		if s * (s + 1) / 2 > n:
			ans = s
			break
		else:
			s += 1
	print(s - 1)


n = int(input())
for j in range(n):
	a = 0
	k = 0
	i = 1
	b = int(input())
	while b >= a:
		k = k + 1
		a += i
		i = k + 1
	print(k - 1)


for _ in range(int(input())):
	x = int(input())
	c = 0
	s = 0
	for i in range(1, 10 ** 9):
		if i + s < x:
			s = i + s
			c += 1
		elif i + s == x:
			s = i + s
			c += 1
			break
		elif i + s > x:
			break
	print(c)


for _ in range(int(input())):
	n = int(input())
	c = 0
	i = 1
	while n >= 0 and i <= n:
		n = n - i
		i = i + 1
		c = c + 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	counter = 0
	x = 1
	while n > 0:
		n = n - x
		if n >= 0:
			counter = counter + 1
		else:
			break
		x = x + 1
	print(counter)


for _ in range(int(input())):
	n = int(input())
	count = 0
	flag = True
	while flag:
		if n <= 0:
			flag = False
		else:
			count += 1
			n -= count
	if n < 0:
		print(count - 1)
	else:
		print(count)


f = int(input())
for m in range(f):
	m = 1
	g = 0
	n = int(input())
	for m in range(1, n + 1):
		m = m * (m + 1) / 2
		if m > n:
			break
		else:
			g += 1
	print(g)


for _ in range(int(input())):
	N = int(input())
	total_line = 0
	i = 0
	while N > 0:
		i = i + 1
		if N >= i:
			total_line = total_line + 1
			N = N - i
		elif N < i:
			break
	print(total_line)


for _ in range(int(input())):
	s = int(input())
	t = -1 + (1 + 8 * s) ** 0.5
	print(int(t / 2))


for _ in range(int(input())):
	coins = int(input())
	i = 1
	row = 0
	while coins >= i:
		coins = coins - i
		i = i + 1
	print(i - 1)


t = int(input())
for i in range(t):
	n = int(input())
	sum = 0
	if n == 1:
		print(1)
	else:
		for j in range(1, n):
			sum = sum + j
			if sum == n:
				print(j)
				break
			elif sum > n:
				print(j - 1)
				break


import math
T = int(input())
for i in range(T):
	N = int(input())
	(left, right) = (0, N)
	while left < right:
		mid = (left + right + 1) // 2
		summation = mid * (mid + 1) // 2
		if summation <= N:
			left = mid
		else:
			right = mid - 1
	print(left)


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


t = int(input())
for _ in range(t):
	s = int(input())
	now = s + 1 // 2
	high = s
	low = 1
	while low < now:
		if now * (now + 1) < s * 2:
			low = now
			now = (low + high) // 2
		elif now * (now + 1) > 2 * s:
			high = now
			now = (low + high) // 2
		else:
			break
	print(now)


n = int(input())
for i in range(n):
	a = int(input())
	i = 1
	count = 0
	for i in range(1, a + 1):
		i = i * (i + 1) / 2
		if i > a:
			break
		else:
			count += 1
	print(count)


for _ in range(int(input())):
	x = int(input())
	ans = 0
	count = 0
	for i in range(1, 10 ** 6):
		ans += i
		if ans <= x:
			count = i
		else:
			break
	print(count)


T = int(input())
for _ in range(T):
	N = int(input())
	c = 0
	for i in range(1, N + 1):
		i = i * (i + 1) // 2
		if i > N:
			break
		else:
			c = c + 1
	print(c)


for i in range(int(input())):
	n = int(input())
	awl = 1
	hei = 0
	while True:
		if n - awl >= 0:
			n -= awl
			awl += 1
			hei += 1
		else:
			break
	print(hei)


for i in range(int(input())):
	n = int(input())
	i = 0
	p = 0
	while i < n + 1:
		if n >= i * ((i + 1) / 2):
			p = i
			i += 1
		else:
			break
	print(p)


def count(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	n = int(input())
	found = False
	(low, high) = (1, n)
	mid = 0
	while low <= high:
		mid = (low + high) // 2
		c = count(mid)
		if c == n:
			print(mid)
			found = True
			break
		elif c > n:
			high = mid - 1
		else:
			low = mid + 1
	if not found:
		if c > n:
			print(mid - 1)
		else:
			print(mid)


for _ in range(int(input())):
	n = int(input())
	c = 0
	for i in range(1, n + 1):
		n = n - i
		if n >= 0:
			c += 1
		if n < i:
			print(c)
			break


for z in range(int(input())):
	t = int(input())
	n = x = 0
	for i in range(1, 1000000):
		t -= i
		if t >= 0:
			x += 1
		else:
			print(x)
			break


for _ in range(int(input())):
	n = int(input())
	count = 0
	for i in range(n):
		n = n - i
		if n - i >= 0 and i < n:
			count += 1
		else:
			break
	print(count)


for i in range(int(input())):
	a = int(input())
	n = 0
	while n * (n + 1) // 2 < a:
		n = n + 1
	if n * (n + 1) // 2 == a:
		print(n)
	else:
		print(n - 1)


from math import sqrt

def IntPart(n):
	res = int((sqrt(8 * n + 1) - 1) / 2)
	return res
for _ in range(int(input())):
	n = int(input())
	print(IntPart(n))


t = int(input())
for i in range(t):
	n = int(input())
	low = 1
	high = n
	while low <= high:
		mid = (low + high) // 2
		res = mid * (mid + 1) // 2
		if res <= n:
			ans = mid
			low = mid + 1
		else:
			high = mid - 1
	print(ans)