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

Chef lives in Chefcity. Chefcity can be represented as a straight line with Chef's house at point 0 on this line. There is an infinite number of subway stations in Chefcity, numbered by positive integers. The first station is located at point 1 and for each i ≥ 1, the distance between stations i and i+1 is equal to i+1. (Station i+1 is always located at a higher coordinate than station i, i.e., the subway stations are located at points 1, 3, 6, 10, 15 etc.)

Subway trains in Chefcity allow Chef to move between any pair of adjacent stations in one minute, regardless of the distance between them. Chef can also move by walking; his walking speed is one unit of distance in one minute. Chef can enter or exit the subway at any station.

Chef has decided to go to the cinema. The only cinema in Chefcity is located at point X. (Note that the cinema can be placed at the same point as a subway station.) Help Chef determine the minimum possible time required to get to the cinema from his house.

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

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single integer X.

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

For each test case, print a single line containing one integer - the minimum possible travel time.

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

$1 ≤ T ≤ 200$
$1 ≤ X ≤ 10^{9}$

----- Sample Input 1 ------ 
4
1
2
3
9
----- Sample Output 1 ------ 
1
2
2
5
----- explanation 1 ------ 
Example case 4: Chef will walk from x = 0 to x = 1 in one minute, then he will enter the subway and move from station 1 (at x = 1) to station 2 (at x = 3) in one minute, then from station 2 to station 3 (at x = 6) in one minute, from station 3 to station 4 (at x = 10) in one minute, and finally, he will walk from x = 10 to x = 9 in one minute, which makes the total travel time 5 minutes.

Difficulty: MEDIUM
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
import math
for _ in range(int(input())):
	x = int(input())
	k = math.sqrt(2 * x + 1 / 4) - 1 / 2
	(ceil, floor) = (math.ceil(k), math.floor(k))
	(sum_max, sum_min) = (ceil * (ceil + 1) // 2, floor * (floor + 1) // 2)
	print(min(floor + abs(x - sum_min), ceil + abs(sum_max - x)))


def sear(i):
	i2 = 1
	p2 = 0
	listr = []
	while p2 < i:
		p2 = i2 * (i2 + 1) // 2
		i2 = i2 + 1
	return i2 - 1

def lister(o):
	i = 1
	p = 0
	ans = 0
	listr = []
	while p <= o:
		p = i * (i + 1) // 2
		i = i + 1
	listr.append((i - 2) * (i - 1) // 2)
	listr.append(p)
	if o in listr:
		return sear(o)
	if o - listr[0] <= listr[1] - o:
		return sear(listr[0]) + o - listr[0]
	if o - listr[0] > listr[1] - o:
		return sear(listr[1]) + listr[1] - o
i = int(input())
listk = []
for _ in range(i):
	x = int(input())
	listk.append(lister(x))
for ele in listk:
	print(ele)


for i in range(int(input())):
	x = int(input())
	y = 0
	time = 0
	prev = 0
	while True:
		time += 1
		prev = y
		y += time
		if y > x or x == y:
			break
	print(min(time + (x - prev) - 1, time + (y - x)))


n = int(input(''))
for j in range(n):
	x = int(input(''))
	lst = []
	dist = 0
	i = 1
	mins = 0
	if x == 1:
		print(1)
	else:
		while True:
			dist += i
			if dist >= x:
				diff = dist - x
				break
			diff = x - dist
			lst.append(diff)
			i += 1
		minimum = min(lst)
		if diff < minimum:
			mins = diff + i
		else:
			mins = minimum + i - 1
		print(mins)


n = int(input())
for j in range(n):
	inp = int(input())
	x = 0
	i = 0
	while True:
		if x >= inp:
			x = x - i
			break
		i += 1
		x += i
	if inp - x <= x + i - inp:
		time = i - 1 + inp - x
	else:
		x = x + i
		time = i + x - inp
	print(time)


for i in range(int(input())):
	x = int(input())
	a = 0
	b = 0
	c = 0
	while True:
		c += 1
		a = b
		b += c
		if a <= x and b > x:
			break
	print(min(c + x - a - 1, c + b - x))


for t in range(int(input())):
	x = int(input())
	time = 0
	st = 0
	sub = 0
	while sub + st + 1 <= x:
		st += 1
		sub += st
		time += 1
	if x - sub <= sub + st + 1 - x:
		time += x - sub
	else:
		time += 1 + sub + st + 1 - x
	print(time)


for _ in range(int(input())):
	x = int(input())
	dist = 0
	i = 1
	count = 0
	while dist + i < x:
		dist += i
		i += 1
		count += 1
	count += min(x - dist, i - (x - dist) + 1)
	print(count)


output = ''
for _ in range(int(input())):
	x = int(input())
	mystery = 2 * x
	i = 0
	while i ** 2 < mystery:
		i += 1
	t = i - 1
	dist = int(t * (t + 1) / 2)
	remain = x - dist
	t += abs(remain)
	output += str(t) + '\n'
print(output)


import math
t = int(input())
a = 0.5
b = 0.5
for ti in range(t):
	x = int(input())
	c = -x
	delta = b ** 2 - 4 * a * c
	x2 = -b + math.sqrt(delta)
	n_floor = math.floor(x2)
	n_ceil = math.ceil(x2)
	pos_floor = n_floor * (n_floor + 1) / 2
	pos_ceil = n_ceil * (n_ceil + 1) / 2
	time_floor = int(n_floor + abs(pos_floor - x))
	time_ceil = int(n_ceil + abs(pos_ceil - x))
	if time_floor > time_ceil:
		print(time_ceil)
	else:
		print(time_floor)


for i in range(int(input())):
	x = int(input())
	i = 0
	j = 1
	t = -1
	d = 0
	while x > i:
		i = i + j
		j = j + 1
		t = t + 1
	if abs(i - x) >= abs(x - (i - j + 1)):
		t = t - 1
		d += abs(x - (i - j + 1))
	else:
		d = abs(i - x)
	print(t + 1 + d)


import math
tests = int(input())
for i in range(tests):
	position = int(input())
	approx = math.floor((2 * position) ** 0.5)
	while approx * (approx + 1) < position:
		approx += 1
	distance = approx + abs(position - approx * (approx + 1) // 2)
	approx -= 1
	distance = min(distance, approx + abs(position - approx * (approx + 1) // 2))
	print(distance)


t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	i = 1
	num = 0
	prev = 0
	while num <= n:
		prev = num
		num = num + i
		i = i + 1
		count = count + 1
	if abs(prev - n) > num - n:
		print(num - n + count)
	else:
		print(abs(prev - n) + count - 1)
	count = 0


t = int(input())
for _ in range(t):
	x = int(input())
	z = 2 * x
	c = int(z ** (1 / 2))
	if c * (c + 1) <= z:
		a = c
	else:
		a = c - 1
	g = a * (a + 1) // 2
	f = (a + 1) * (a + 2) // 2
	print(min(a + (x - g), a + 1 + (f - x)))


t = int(input())
for _ in range(t):
	x = int(input())
	if x == 1:
		print(1)
	else:
		l = []
		l.append(1)
		i = 2
		while True:
			l.append(l[-1] + i)
			i += 1
			if l[-1] >= x:
				break
		if x == l[-1]:
			print(len(l))
		else:
			a = len(l) - 1 + (x - l[-2])
			b = len(l) + (l[-1] - x)
			print(min(a, b))


T = int(input())
for i in range(0, T):
	a = int(input())
	tt = 1
	d = 1
	while d < a:
		tt += 1
		d += tt
	bb = tt
	dd = d - bb
	bb -= 1
	print(min(tt + (d - a), bb + (a - dd)))


for _ in range(int(input())):
	n = int(input())
	i = 0
	ans = 0
	while n > ans:
		i += 1
		ans += i
	pre_ans = ans - i
	pre_i = i - 1
	if n == ans:
		print(i)
	elif ans - n + i < n - pre_ans + pre_i:
		print(ans - n + i)
	else:
		print(n - pre_ans + pre_i)


import sys
for xx in range(int(sys.stdin.readline())):
	x = int(sys.stdin.readline())
	i = 1
	a = 0
	while True:
		a += i
		if a > x:
			ans = i + min(x - a + i - 1, a - x)
			print(ans)
			break
		elif a == x:
			print(i)
			break
		i += 1


for xx in range(int(input())):
	x = int(input())
	i = 1
	a = 0
	r = (0, 0)
	while True:
		a += i
		if a > x:
			r = (a - i, a)
			ans = i + min(x - a + i - 1, a - x)
			print(ans)
			break
		elif a == x:
			print(i)
			break
		i += 1


for _ in range(int(input())):
	x = int(input())
	ans = 0
	i = 0
	while x > ans:
		i += 1
		ans += i
	pre_ans = ans - i
	pre_i = i - 1
	if ans - x + 1 > x - pre_ans:
		sol = pre_i + (x - pre_ans)
	elif ans - x + 1 <= x - pre_ans:
		sol = i + (ans - x)
	elif ans == x:
		sol = i
	print(sol)


import math
for tc in range(int(input())):
	n = int(input())
	p = int(((8 * n + 1) ** 0.5 - 1) // 2)
	print(p + min(n - p * (p + 1) // 2, (p + 1) * (p + 2) // 2 - n + 1))


for _ in range(int(input())):
	n = int(input())
	k = (1 + 8 * n) ** 0.5 - 1
	k = int(k // 2)
	p = k * (k + 1) // 2
	q = (k + 1) * (k + 2) // 2
	print(min(n - p + k, q - n + k + 1))


import math as m
t = int(input())
for i in range(t):
	x = int(input())
	if x < 3:
		print(x)
	else:
		c = m.ceil((m.sqrt(1 + 8 * x) - 1) / 2)
		f = m.floor((m.sqrt(1 + 8 * x) - 1) / 2)
		n1 = c * (c + 1) // 2
		n2 = f * (f + 1) // 2
		print(min(c + abs(n1 - x), f + abs(n2 - x)))


import math
t = int(input())
for i in range(t):
	x = int(input())
	res = 0
	dis = 0
	no = 1
	while dis + no <= x:
		res += 1
		dis += no
		no += 1
	res += min(x - dis, no - (x - dis) + 1)
	print(res)


T = int(input())
for _ in range(T):
	N = int(input())
	j = 1
	while j * (j + 1) < 2 * N:
		j += 1
	if j * (j + 1) == N:
		print(j)
		continue
	j -= 1
	A = j * (j + 1)
	A //= 2
	j += 1
	B = j * (j + 1)
	B //= 2
	print(min(j - 1 + N - A, j - N + B))


from math import *
t = int(input())
for i in range(t):
	x = int(input())
	if x == 1:
		print(1)
		continue
	else:
		j = 1
		temp = 2 * x
		while j * (j + 1) < temp:
			j = j + 1
		if j * (j + 1) == temp:
			print(j)
			continue
		j = j - 1
		temp1 = j * (j + 1)
		temp1 = int(temp1 / 2)
		temp2 = (j + 1) * (j + 2)
		temp2 = int(temp2 / 2)
		print(min(j + x - temp1, j + 1 - x + temp2))


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())
from math import sqrt

def tri(n):
	return n * (n + 1) // 2

def reverse_tri(n):
	return int((sqrt(8 * n + 1) - 1) / 2)

def solve(x):
	l = reverse_tri(x)
	(lt, ht) = (tri(l), tri(l + 1))
	return min(l + x - lt, l + 1 + (ht - x))

def do_codechef():
	for t in rii():
		print(solve(ii()))
do_codechef()
exit()


for _ in range(int(input())):
	x = int(input())
	ans = 0
	curr_dist = 0
	i = 1
	while curr_dist + i <= x:
		ans += 1
		curr_dist += i
		i += 1
	ans += min(x - curr_dist, i - (x - curr_dist) + 1)
	print(ans)


import math
t = int(input())
for _ in range(t):
	x = int(input())
	n2 = (math.sqrt(1 + 8 * x) - 1) // 2
	if x == 1:
		print(1)
	else:
		dis1 = (n2 * n2 + n2) // 2
		dis2 = ((n2 + 1) * (n2 + 1) + (n2 + 1)) // 2
		ans1 = 1 + (n2 - 1) + abs(x - dis1)
		ans2 = 1 + n2 + abs(x - dis2)
		print(min(int(ans1), int(ans2)))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	x = int(input())
	count = 0
	if x == 1:
		print(1)
		continue
	for i in range(0, x + 1):
		if i * (i + 1) // 2 >= x:
			count = i - 1 + min(abs(x - (i - 1) * i // 2), abs(x - i * (i + 1) // 2))
			if abs(x - (i - 1) * i // 2) > abs(x - i * (i + 1) // 2):
				count += 1
			print(count)
			break


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(1)
	else:
		c = 1
		s = 1
		while s < n:
			s += c + 1
			c += 1
		if s - n < n - (s - c):
			print(c + (s - n))
		else:
			print(c - 1 + (n - (s - c)))


try:
	t = int(input())
	while t != 0:
		x = int(input())
		if x == 1:
			print(1)
			t = t - 1
			continue
		i = 1
		temp = 1
		while temp < x:
			temp = temp + i + 1
			i += 1
		if temp - x < x - (temp - i):
			print(i + (temp - x))
		else:
			print(i - 1 + (x - (temp - i)))
		t = t - 1
except:
	pass


T = int(input().strip())
while T > 0:
	x = int(input().strip())
	station = 0
	previousstation = 0
	for i in range(x):
		previousstation = station
		station += i + 1
		if x == station:
			print(i + 1)
			break
		elif x == station + 1:
			print(i + 2)
			break
		elif x < station:
			if abs(station - x) < abs(previousstation - x):
				timetaken = i + abs(station - x) + 1
				print(timetaken)
				break
			else:
				timetaken = i + abs(previousstation - x)
				print(timetaken)
				break
	T = T - 1


chef_home = 0
first_station_point = 1
adjacent_station_point = 0
station_count = 1
train_mins = 1
for tc in range(int(input())):
	cinema_point = int(input())
	while cinema_point >= first_station_point:
		if cinema_point == first_station_point:
			print(train_mins)
			break
		adjacent_station_point = station_count + 1 + first_station_point
		if cinema_point > first_station_point and cinema_point < adjacent_station_point:
			point = first_station_point + 1
			count = 0
			for i in range(point, cinema_point + 1):
				count += 1
			point = adjacent_station_point
			count1 = 0
			for i in range(point, cinema_point - 1, -1):
				count1 += 1
			if count1 <= count:
				by_walk_mins = count1
			else:
				by_walk_mins = count
			print(train_mins + by_walk_mins)
			break
		station_count += 1
		train_mins += 1
		first_station_point = adjacent_station_point


T = int(input())
for i in range(T):
	n = int(input())
	if n == 1:
		print(1)
	else:
		i = 1
		j = 1
		while j < n:
			j = j + i + 1
			i += 1
		if j - n < n - (j - i):
			print(i + (j - n))
		else:
			print(i - 1 + (n - (j - i)))


t = int(input())
for _ in range(t):
	x = int(input())
	s = 1
	i = 1
	while s < x:
		i = i + 1
		s = s + i
	ma = s - i
	mb = s
	if abs(ma - x) <= abs(mb - x):
		ans = i - 1 + x - ma
	else:
		ans = i + mb - x
	print(ans)


for _ in range(int(input())):
	x = int(input())
	l = [1, 3]
	for i in range(3, x):
		p = i * (i + 1) // 2
		l.append(p)
		if p > x:
			break
	print(min(len(l) + l[-1] - x, len(l) - 1 + x - l[-2]))


t = int(input())
for _ in range(t):
	n = int(input())
	res = 0.5 * (8 * n + 1) ** 0.5 - 0.5
	res = int(res)
	alt = res + 1
	if res + (n - (res ** 2 + res) // 2) < alt + ((alt ** 2 + alt) // 2 - n):
		print(res + (n - (res * res + res) // 2))
	else:
		print(alt + (alt * alt + alt) // 2 - n)


for _ in range(int(input())):
	X = int(input())
	station = 0
	i = 0
	if X == 1:
		print(1)
	elif X == 2:
		print(2)
	else:
		while station < X:
			i += 1
			station += i
		prev = station - i
		if station - X >= X - prev:
			print(i - 1 + X - prev)
		else:
			print(i + station - X)


for _ in range(int(input())):
	n = int(input())
	sub = int((n * 2) ** 0.5)
	print(min(sub + abs(n - sub * (sub + 1) // 2), sub - 1 + abs(n - (sub - 1) * sub // 2), sub + 1 + abs(n - (sub + 1) * (sub + 2) // 2)))


from math import sqrt

def nsum(n):
	return n * (n + 1) // 2
t = int(input())
for _ in range(t):
	x = int(input())
	n = int(sqrt(x * 2)) - 1
	while n * (n + 1) < x * 2:
		n = n + 1
	d1 = n - 1 + x - nsum(n - 1)
	d2 = n + nsum(n) - x
	print(min(d1, d2))


import math
for _ in range(int(input())):
	tn = int(input())
	a = 1
	b = 1
	c = 2 * tn
	time = 0
	pos = (-1 + math.sqrt(1 + 4 * c)) / 2
	pos = round(pos)
	pre_pos = pos - 1
	station = int(pos * (pos + 1) / 2)
	pre_station = int(pre_pos * (pre_pos + 1) / 2)
	if (station + pre_station) / 2 >= tn:
		pos = pre_pos
	time += pos
	station = int(pos * (pos + 1) / 2)
	time += abs(tn - station)
	print(time)


for _ in range(int(input())):
	x = int(input())
	t = (-1 + int((1 + 8 * x) ** 0.5)) // 2
	t_1 = t * (t + 1) // 2
	t_2 = t_1 + (t + 1)
	a_1 = t + (x - t_1)
	a_2 = t + 1 + (t_2 - x)
	print(min(a_1, a_2))


import math
for i in range(int(input())):
	a = int(input())
	z = (math.sqrt(1 + 8 * a) - 1) // 2
	y = z + 1
	print(int(min(z + a - z * (z + 1) // 2, y + y * (y + 1) // 2 - a)))


import math
t = int(input())
while t:
	x = int(input())
	n = (-1 + math.sqrt(1 + 8 * x)) / 2
	(a, b) = (math.floor(n), math.ceil(n))
	(p, q) = (int(a * (a + 1) / 2), int(b * (b + 1) / 2))
	if a == b:
		c = int(n)
	elif x - p <= q - x:
		c = a + x - p
	else:
		c = b + q - x
	print(c)
	t -= 1


l = [0]
for i in range(1, 44722):
	l.append(l[-1] + i)
t = int(input())
while t > 0:
	n = int(input())
	for i in range(1, 44722):
		if l[i] >= n:
			x = l[i] - n
			break
	if n - l[i - 1] <= x:
		x = n - l[i - 1]
		i -= 1
	print(i + x)
	t -= 1


import math
test = int(input())
for _ in range(test):
	a = int(input())
	z = (math.sqrt(1 + 8 * a) - 1) // 2
	y = z + 1
	print(int(min(z + a - z * (z + 1) // 2, y + y * (y + 1) // 2 - a)))


for _ in range(int(input())):
	X = int(input())
	l = [1, 3]
	for i in range(3, X):
		p = i * (i + 1) // 2
		l.append(p)
		if p > X:
			break
	t1 = len(l) + l[-1] - X
	t2 = len(l) - 1 + X - l[-2]
	print(min(t1, t2))


for _ in range(int(input())):
	X = int(input())
	l = [0, 1]
	while True:
		p = len(l) + l[-1]
		l.append(p)
		if p > X:
			break
	t1 = len(l) - 1 + l[-1] - X
	t2 = len(l) - 2 + X - l[-2]
	print(min(t1, t2))


from math import *
from collections import *
from itertools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(1000000)
d = defaultdict(lambda : 0, {})

def io():
	return map(int, input().split())

def op():
	return list(map(int, input().split()))

def o():
	return int(input())

def r(x):
	if type(x) == int:
		return range(x)
	else:
		return range(len(x))

def kl(con, x=0):
	if x == 0:
		print('Yes') if con else print('No')
	elif x == 1:
		print('yes') if con else print('no')
	elif x == 2:
		print('YES') if con else print('NO')
MOD = 1000000007
MAX = float('inf')
MIN = -float('inf')
p = input

def bs(n):
	(l, r) = (0, 10 ** 9)
	while l <= r:
		m = (l + r + 1) // 2
		z = m * (m + 1) // 2
		if z == n:
			return m
		elif l == r:
			z1 = m * (m + 1) // 2
			z2 = (m + 1) * (m + 2) // 2
			if abs(z1 - n) > abs(z2 - n):
				return m + 1
			else:
				return m
		elif z < n:
			l = m
		else:
			r = m - 1
	return -1
for i in range(int(input())):
	n = o()
	x = bs(n)
	ans = x
	ans += abs(x * (x + 1) // 2 - n)
	print(ans)


testcase = int(input())
for z in range(testcase):
	X = int(input())
	li = [0]
	nums = 1
	while li[-1] < X:
		li.append(li[nums - 1] + nums)
		nums = nums + 1
	if li[-1] == X:
		print(nums - 1)
		continue
	if li[-1] - X > X - li[-2]:
		print(nums - 2 + X - li[-2])
	if li[-1] - X < X - li[-2]:
		print(nums - 1 + li[-1] - X)
	if li[-1] - X == X - li[-2]:
		print(nums - 2 + X - li[-2])


from bisect import bisect_left
x = [0] * 50000
for i in range(50000):
	x[i] = x[i - 1] + (i + 1)
for j in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		index = bisect_left(x, n)
		a = index
		b = index - 1
		c = b + abs(x[b] - n) + 1
		d = a + abs(x[a] - n) + 1
		print(min(c, d))


T = int(input())
for i in range(T):
	x = int(input())
	(s, t, c) = (0, 0, 0)
	while True:
		if t == x:
			print(s)
			break
		if c < x and x < t:
			if t - x < x - c:
				print(t - x + s)
			else:
				print(x - c + s - 1)
			break
		s += 1
		c = t
		t += s


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


d = {}
count = 1
other = 2
for i in range(1, 10 ** 9):
	d[count] = i
	count += other
	other += 1
	if count > 10 ** 9 * 2:
		break
for _ in range(int(input())):
	n = int(input())
	ans = 0
	if n in d:
		print(d[n])
	else:
		minus = n
		plus = n
		co = 0
		while True:
			minus -= 1
			plus += 1
			co += 1
			if minus in d:
				ans += co
				ans += d[minus]
				print(ans)
				break
			elif plus in d:
				ans += co
				ans += d[plus]
				print(ans)
				break


stations_li = [1]
for i in range(int(input())):
	cinema_loc = int(input())
	while stations_li[-1] < cinema_loc:
		nextStation = stations_li[-1] + len(stations_li) + 1
		stations_li.append(nextStation)
	mins = 1
	if cinema_loc > 1:
		train_time = len(stations_li)
		use_last = train_time + stations_li[-1] - cinema_loc
		second_last = train_time - 1 + cinema_loc - stations_li[-2]
		mins = min(use_last, second_last)
	print(mins)


for t in range(int(input())):
	x = int(input())
	i = (-1 + (4 + 8 * x) ** 0.5) // 2
	time = min(i + x - i * (i + 1) // 2, i + (i + 2) * (i + 1) // 2 - x + 1)
	print(int(time))


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	elif n == 3:
		print(2)
	elif n == 4:
		print(3)
	else:
		b = int((sqrt(8 * n + 1) - 1) // 2)
		p = b * (b + 1) // 2
		q = (b + 2) * (b + 1) // 2
		print(min(b + n - p, b + 1 + q - n))


t = int(input())
while t:
	x = int(input())
	time = 0
	arr = []
	arr.append(0)
	for i in range(1, x + 1):
		st = arr[i - 1] + i
		arr.append(st)
		if x == st:
			time = i
			break
		if st > x:
			difflarge = st - x
			diffsmall = x - arr[i - 1]
			if difflarge == diffsmall:
				time = i - 1 + difflarge
				break
			if difflarge > diffsmall:
				time = i - 1 + diffsmall
			else:
				time = i + difflarge
			break
	print(time)
	t = t - 1


from math import sqrt
for _ in range(int(input())):
	X = int(input())
	if X == 1:
		print(1)
	elif X == 2:
		print(2)
	elif X == 3:
		print(2)
	elif X == 4:
		print(3)
	else:
		a = int((sqrt(8 * X + 1) - 1) // 2)
		p = a * (a + 1) // 2
		q = (a + 2) * (a + 1) // 2
		print(min(a + X - p, a + 1 + q - X))


def CO92SUBW(x):
	from math import sqrt
	n = (-1 + int(sqrt(1 + 8 * x))) // 2
	nx = (n + 1) * (n + 2) // 2
	return min(x - n * (n + 1) // 2 + n, 1 + n + (nx - x))
t = int(input())
for _ in range(t):
	x = int(input())
	print(CO92SUBW(x))


import bisect
T = int(input())
lst = [0, 1]
lim = 2 * 10 ** 9
i = 2
while True:
	lst.append(lst[-1] + i)
	i += 1
	if lst[-1] > lim:
		break
for z in range(T):
	N = int(input())
	left_idx = bisect.bisect_left(lst, N)
	print(min(left_idx + abs(N - lst[left_idx]), left_idx - 1 + abs(lst[left_idx - 1] - N)))


from bisect import bisect_left as bl
a = [1] * 50000
for i in range(1, 50000):
	a[i] = a[i - 1] + i + 1
for _ in range(int(input())):
	x = int(input())
	ans = 0
	indx = bl(a, x)
	if a[indx] == x:
		print(indx + 1)
	else:
		print(min(indx + x - a[indx - 1], indx + 1 + a[indx] - x))


TC = int(input())
for _ in range(TC):
	n = int(input())
	if n == 1 or n == 2:
		print(n)
		continue
	x = (int((1 + 8 * n) ** 0.5) - 1) // 2
	y = x + 1
	a = (x * x + x) // 2
	b = (y * y + y) // 2
	if abs(n - a) <= abs(n - b) + 1:
		print(x + abs(n - a))
	else:
		print(y + abs(n - b))


import sys
for i in range(int(sys.stdin.readline())):
	(x, sum, c) = (int(sys.stdin.readline()), 0, 0)
	while x > sum:
		c += 1
		sum = sum + c
	if sum - x < x - sum + c:
		sys.stdout.write(str(c + sum - x) + '\n')
	else:
		sys.stdout.write(str(c - 1 + x - sum + c) + '\n')


for _ in range(int(input())):
	x = int(input())
	i = 1
	l = []
	k = 2
	while i <= x:
		l.append(i)
		i += k
		k += 1
	l.append(i)
	temp = min(l[-2:], key=lambda i: abs(i - x))
	print(l.index(temp) + 1 + abs(temp - x))