Sandu, a teacher in Chefland introduced his students to a new sequence i.e.
0,1,0,1,2,0,1,2,3,0,1,2,3,4........
The Sequence starts from 0 and increases by one till $i$(initially i equals to 1), then repeat itself with $i$ changed to $i+1$
Students being curious about the sequence asks the Nth element of the sequence. Help Sandu to answer the Students

-----Input:-----
- The first-line will contain $T$, the number of test cases. Then the test case follows. 
- Each test case contains a single numbers N.

-----Output:-----
Print the Nth element of the sequence

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N  \leq 10^{18}$

-----Sample Input:-----
5
8
9
20
32
109

-----Sample Output:-----
2
3
5
4
4

Difficulty: interview

Starter code:

Solutions:
from math import sqrt

for _ in range(int(input())):
 n = int(input())

 x = int(sqrt(2 * n))

 while x * (x+1) // 2 <= n:
  x += 1

 while x * (x+1) // 2 > n:
  x -= 1

 n -= x * (x+1) // 2

 print(n)


"""
Problem Statement: https://www.codechef.com/ENCD2020/problems/ECAPR203
Author: striker
"""

import math

def main():
 for test in range(int(input().strip())):
  n = int(input().strip())
  tinv = (1 + int(math.sqrt(1 + 8 * n))) // 2
  print(n - ((tinv * (tinv - 1)) // 2))

def __starting_point():
 main()

__starting_point()

import math
_1_50 = 1 << 50
def isqrt(x):
 if x < 0:
  raise ValueError('square root not defined for negative numbers')
 if x < _1_50:
  return int(math.sqrt(x)) 
 n = int(x)
 if n <= 1:
  return n 

 r = 1 << ((n.bit_length() + 1) >> 1)
 while True:
  newr = (r + n // r) >> 1 
  if newr >= r:
   return r
  r = newr

for i in range(int(input())):
 n=int(input())
 x=(isqrt(4*2*n+1)-1)//2
 
 x=x*(x+1)//2
 print(n-x)


import math

for _ in range(int(input())):
 n = int(input())
 
 def findNumber( n ): 
  
  x = int(math.ceil((-1 + math.sqrt(1
    + 8 * n + 8)) / 2)) 
  x -= 1
   
  b = (x * (x + 1)) // 2 - 1
  
  res = n - b -1 
  
  return res
 ans = findNumber(n)
 print(ans)

# cook your dish here
import math
t=int(input())
while t>0:
 n=int(input())
 k=n+1
 k*=2
 a=math.sqrt(k)
 a=int(a)
 if a*(a+1)>k:
  a-=1 
 b=k-(a*(a+1))
 if b==0:
  c=a-1
 else:
  c=b//2
  c-=1
 print(c)
 t-=1
 
 


# cook your dish here
import math
t = int(input())
for _ in range(t):
 n = int(input())
 x = math.floor((-1 + math.sqrt(1 + 8 * (n))) // 2)
 num = (x * (x+1) // 2) 
 print(n - num)

def do_sum(m):
 return ((m+1)*(m+2))//2-1

def bin_search(n, l, h):
 m = (l+h)//2
 if do_sum(m)<n and do_sum(m+1)>=n:
  return m
 if do_sum(m)<n:
  return bin_search(n, m+1, h)
 return bin_search(n, l, m-1)

t = int(input().strip())
for _ in range(t):
 n = int(input().strip())
 # a = [int(x) for x in input().strip().split()]
 m = bin_search(n,1,10000000000)
 print(n-((m+1)*(m+2))//2)

from math import floor
t = int(input())
for _ in range(t):
 n = int(input())
 t = floor((2*n+1/4)**0.5 - 1/2)
 nt = t*(t+1)//2
 print(int(n-nt))

import math
_1_50 = 1 << 50
def isqrt(x):
 if x < 0:
  raise ValueError('square root not defined for negative numbers')
 if x < _1_50:
  return int(math.sqrt(x)) 
 n = int(x)
 if n <= 1:
  return n 

 r = 1 << ((n.bit_length() + 1) >> 1)
 while True:
  newr = (r + n // r) >> 1 
  if newr >= r:
   return r
  r = newr

for i in range(int(input())):
 n=int(input())
 x=(isqrt(4*2*n+1)-1)//2
 x=x*(x+1)//2
 print(n-x)




#In the Name of God
import math

t = int(input())

for _ in range(t):
 n = int(input())
 x = int(math.sqrt(2*n))
 while(((x*(x+1))//2)-1 >= n):
  x-=1;
 #print(x)
 ini = (x*(x+1))//2
 ini -= 1
 print(int(n-ini-1))

# cook your dish here
import math

def solve(N):
 bucket = math.ceil((math.sqrt(8*N+1)-1)//2)
 return N - (bucket*bucket+bucket)//2


T = int(input())
for _ in range(T):
 N = int(input())
 result = solve(N)
 print(result)

# cook your dish here
import math
for _ in range(int(input())):
 N=int(input())
 t=int(math.sqrt(2*N+2))
 if ((t*t+1)<N):
  t=t+1
 if(t&1==1):
  print(N%t)
 else:
  k=N%t
  if(k<t//2):
   print(k+t//2)
  else:
   print(k-t//2)


for n in range(int(input())):
 x=int(input())
 v=x+1
 j=-1+int((8*v)**.5)
 j//=2
 d=j*(j+1)//2
 if d==v:
  print(j-1)
 else:
  print(v-d-1)


# cook your dish here
t = int(input())
for i in range(t):
 n = int(input())
 x = int((((8*(n+1)+1)**0.5) - 1)/2)
 d = (8*(n+1)+1)**0.5
 if (d-int(d)==0):
  print(x-1)
 else:
  f = (x*(x+1))//2 
  c = n-f
  print(c)


#code
import math
t=int(input())
while(t>0):
 t-=1
 n=int(input())
 n-=1
 n1=(int(math.sqrt(8*n+1))-1)//2
 i=n1*(n1+1)//2-1
 if(n1+1+i==n):
  print(0)
 else:
  print(n-i)

t=int(input())
for i in range(t):
 n=int(input())
 term=(-1+((8*n+9)**0.5))/2
 # print('term is '+str(term))
 if term==int(term):
  ans=int(term-1)
  # print('yo')
  # print(str(term)+' '+str(int(term)))
 else:
  term=int(term)
  summ=((term*(term+1))//2)-1
  # print('summ is '+str(summ))
  ans=n-summ-1
 print(ans)

# cook your dish here
from collections import defaultdict
import math
p=int(input())
while p>0:
 n=int(input())
 #n-=1
 t=math.floor(((2*n+1)**0.5)+0.5)
 res=0.5*(t-(t**2)+2*n)
 print(int(res))
 p-=1


 


# cook your dish here
#ecapr203

try:
# if(True):
 for _ in range(int(input())):
  n=int(input())
  k=int((((9+(8*n))**(0.5))-1)/2)
  m=((k-1)*(k+2))//2
  d=n-m
  if(d==0):
   print(k-1)
  else:
   print(d-1)
except:
 pass

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


import math
t = int(input())
while t:
 n = int(input())
 c = 0
 i = (1 + math.ceil((9 + 8 * n)**0.5) - 1) // 2
 # print(i)
 c = (i * (i + 1) // 2) - 1
 # print(c)
 print(int(i - (c - n) - 1))
 t-=1

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

t=int(input())
for it in range(t):
 n=int(input())
 p=int(((8*n+1)**0.5-3)/2)
 print(n-((p+1)*(p+2))//2)

import math
def getk(n):
 exp=(9+8*n)**0.5
 exp-=1
 exp=exp//2
 # print(math.floor(exp))
 return math.floor(exp)
t=int(input())
while(t):
 n=int(input())
 k=int(getk(n))
 offset= int(n-(k*(k+1)//2-1))
 if(offset==0):
  offset=k
 print(offset-1)
 t-=1