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

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)


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)


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


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())
	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
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
	ini = x * (x + 1) // 2
	ini -= 1
	print(int(n - ini - 1))


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)


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) ** 0.5)
	j //= 2
	d = j * (j + 1) // 2
	if d == v:
		print(j - 1)
	else:
		print(v - d - 1)


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)


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
	if term == int(term):
		ans = int(term - 1)
	else:
		term = int(term)
		summ = term * (term + 1) // 2 - 1
		ans = n - summ - 1
	print(ans)


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


try:
	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
	c = i * (i + 1) // 2 - 1
	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
	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