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 1st row.
- then puts 2 coins in the 2nd row.
- then puts 3 coins in the 3rd 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 ≤ 109

-----Subtasks-----
- Subtask 1 (48 points) : 1 ≤ N ≤ 105
- Subtask 2 (52 points) : 1 ≤ N ≤ 109

-----Example-----
Input3
3
5
7

Output2
2
3

-----Explanation-----
- 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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = eval(input())

def moneda(m):
	h = 1
	triange = []
	while m >= h:
		triange.append(h)
		m -= h
		h += 1
	return len(triange)
triangulo = []
for i in range(t):
	n = eval(input())
	triangulo.append(n)
for i in triangulo:
	print(moneda(i))


for tests in range(eval(input())):
	N = eval(input())
	print(int((-1 + (1 + 8 * N) ** 0.5) / 2))


MAX = 10 ** 9 + 100
a = []
i = 1
x = 1
while x <= MAX:
	x = i * (i + 1) / 2
	a.append(x)
	i += 1
l = len(a)
t = int(input())
while t != 0:
	n = int(input())
	i = 0
	while n >= a[i] and i < l:
		i += 1
	print(i)
	t -= 1


from math import sqrt
for __ in range(eval(input())):
	print(int((-1 + sqrt(1 + 8 * eval(input()))) / 2))


r = int(input())
L = []
for i in range(r):
	x = int(input())
	L.append(x)
for i in range(r):
	print(int(((8 * L[i] + 1) ** 0.5 - 1) / 2))


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


from sys import stdin, stdout
from math import sqrt, floor, ceil, log
from collections import defaultdict, Counter

def read():
	return stdin.readline().rstrip()

def write(x):
	stdout.write(str(x))

def endl():
	write('\n')
(data, x) = ([1], 1)
while data[-1] <= 10 ** 9:
	x += 1
	data.append(x * (x + 1) / 2)
for T in range(int(read())):
	(n, c) = (int(read()), 0)
	for i in data:
		if i <= n:
			c += 1
		else:
			break
	write(c)
	endl()


test = int(input())
a = 0
while a < test:
	a = a + 1
	n = int(input())
	sum = 0
	if n == 1:
		print('1')
	else:
		for i in range(1, n):
			sum = sum + i
			if sum == n:
				print(i)
				break
			elif sum > n:
				print(i - 1)
				break
			else:
				pass


from math import sqrt
itr = int(input())
for i in range(itr):
	n = int(input())
	j = int(sqrt(n * 2))
	while j > 0:
		if j * (j + 1) / 2 <= n:
			print(j)
			break
		j -= 1


__author__ = 'Deepak'
t = eval(input())
while t > 0:
	t -= 1
	a = eval(input())
	k = 0
	while a - k >= 0:
		a -= k
		k += 1
	print(k - 1)


a = eval(input())
for i in range(a):
	n = eval(input())
	count = 1
	element = 0
	flag = 0
	while n >= count:
		flag += 1
		n -= count
		element += count
		count += 1
	print(flag)


import bisect
comb = [0] * 100001
comb[1] = 1
for i in range(1, 100001):
	comb[i] = comb[i - 1] + i
for _ in range(eval(input())):
	n = eval(input())
	index = bisect.bisect_left(comb, n)
	if comb[index] == n:
		print(index)
	else:
		print(index - 1)


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


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


def findHeight():
	tests = int(input())
	for t in range(tests):
		n = int(input())
		sumd = 0
		res = 0
		for i in range(1, n + 1):
			sumd += i
			if sumd == n:
				res = i
				break
			elif sumd > n:
				res = i - 1
				break
		print(res)
findHeight()


a = [1]

def lub(n):
	for i in range(len(a) - 1, -1, -1):
		if a[i] <= n:
			return str(i + 1)
for tc in range(int(input())):
	n = int(input())
	if n < a[len(a) - 1]:
		print(lub(n))
	else:
		while True:
			l = len(a) + 1
			a.append(l * (l + 1) / 2)
			if a[l - 1] > n:
				break
		print(lub(n))


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


i = 0
l = []
while i < 10 ** 3:
	l.append(i * (i + 1) / 2)
	i = i + 1
t = int(input())
for _ in range(t):
	x = int(input())
	for i in range(1, len(l)):
		if x == l[i]:
			print(i)
		elif x < l[i] and x > l[i - 1]:
			print(i - 1)
		else:
			pass