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: interview

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))


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))


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)


'''input
3
3
5
7
'''

#~~~~~~~~~~~~~~~~~~~~dwij28 == Abhinav Jha~~~~~~~~~~~~~~~~~~~~#

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()

# cook your code here
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)

# your code goes here
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


# cook your code here
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