Sehr Sus is an infinite hexagonal grid as pictured below, controlled by MennaFadali, ZerooCool and Hosssam.

They love equilateral triangles and want to create $n$ equilateral triangles on the grid by adding some straight lines. The triangles must all be empty from the inside (in other words, no straight line or hexagon edge should pass through any of the triangles).

You are allowed to add straight lines parallel to the edges of the hexagons. Given $n$, what is the minimum number of lines you need to add to create at least $n$ equilateral triangles as described?

Adding two red lines results in two new yellow equilateral triangles.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Then $t$ test cases follow.

Each test case contains a single integer $n$ ($1 \le n \le 10^{9}$) — the required number of equilateral triangles.


-----Output-----

For each test case, print the minimum number of lines needed to have $n$ or more equilateral triangles.


-----Examples-----

Input
4
1
2
3
4567
Output
2
2
3
83


-----Note-----

In the first and second test cases only 2 lines are needed. After adding the first line, no equilateral triangles will be created no matter where it is added. But after adding the second line, two more triangles will be created at once.

In the third test case, the minimum needed is 3 lines as shown below.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Geometry

Sorting

Implementation

Complete search

Greedy algorithms

Mathematics


Solutions:
import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	print(math.ceil(math.sqrt(3 / 2 * int(input()))))


import sys
input = sys.stdin.readline
from bisect import bisect_left

def f(a, b, c):
	(a, b, c) = sorted((a, b, c))
	return (b, a + 1, c, 2 * (b + c))
(a, b, c) = (0, 0, 0)
dp = []
while not dp or dp[-1] < 1000000000.0:
	(a, b, c, v) = f(a, b, c)
	if not dp:
		dp.append(v)
	else:
		dp.append(dp[-1] + v)
for _ in range(int(input())):
	n = int(input())
	ans = bisect_left(dp, n)
	print(ans + 1)


import sys
input = sys.stdin.readline
import math

def solve():
	n = int(input())
	if n <= 6:
		return 2 if n <= 2 else 3
	k = int(math.sqrt(n // 6))
	while 6 * (k + 1) ** 2 < n:
		k += 1
	v = 6 * k ** 2
	if v >= n:
		return 3 * k
	v += 4 * k
	if v >= n:
		return 3 * k + 1
	v += 4 * k + 2
	if v >= n:
		return 3 * k + 2
	return 3 * k + 3
for _ in range(int(input())):
	print(solve())


import sys
DEBUG = False

def check(n):
	k = (n / 2 / 3) ** 0.5
	k = int(k)

	def test(a, b, c):
		if (a * b + a * c + b * c) * 2 >= n:
			print(a + b + c)
			return True
		return False
	if test(k, k, k):
		return
	if test(k, k, k + 1):
		return
	if test(k, k + 1, k + 1):
		return
	if test(k + 1, k + 1, k + 1):
		return

def main(f):
	t = int(f.readline())
	for i in range(t):
		n = int(f.readline())
		check(n)
if DEBUG:
	f = open('input.txt', 'r')
else:
	f = sys.stdin
main(f)
f.close()


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	i = int((n / 6) ** 0.5)
	total = 6 * i ** 2
	add = 4 * i
	i *= 3
	while total < n:
		total += add
		i += 1
		if i % 3 != 0:
			add += 2
	out += str(i) + '\n'
print(out)


import sys
from collections import deque

def rall():
	return sys.stdin.readlines()

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
nlist = []
for ti in range(NT):
	nlist.append((int(rl()), ti))
nlist.sort()
nlist = deque(nlist)
L = [0, 0, 0]
nlines = 0
tot = 0
out = [0] * NT
while len(nlist) > 0:
	nlines += 1
	L[nlines % 3] += 1
	tot += 2 * (L[(nlines + 1) % 3] + L[(nlines + 2) % 3])
	while nlist[0][0] <= tot:
		(_, i) = nlist.popleft()
		out[i] = nlines
		if len(nlist) == 0:
			break
for o in out:
	pr(o)


import math as m
import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	Ammar = int(input())
	SagHai = int(m.sqrt(3 / 2 * Ammar))
	MUEDMDMDMD = 0
	for i in range(SagHai, SagHai + 2):
		if i * i * 2 / 3 >= Ammar:
			MUEDMDMDMD = i
			break
	if Ammar == 1 or Ammar == 2:
		print(2)
	else:
		print(MUEDMDMDMD)


import sys
input = lambda : sys.stdin.readline().strip()
ans = 0
for i in range(int(input())):
	a = int(input())
	f = int((3 / 2 * a) ** 0.5)
	final = 0
	for i in range(f, f + 2):
		if 2 * i ** 2 / 3 >= a:
			final = i
			break
	if a == 1 or a == 2:
		print(2)
	else:
		print(final)


import sys
input = lambda : sys.stdin.readline().strip()
import math as m
ans = 0
for i in range(int(input())):
	a = int(input())
	f = int(m.sqrt(3 / 2 * a))
	final = 0
	for i in range(f, f + 2):
		if 2 * i ** 2 / 3 >= a:
			final = i
			break
	if a == 1 or a == 2:
		print(2)
	else:
		print(final)


from typing import Iterator, List

def solve(triangles: List[int]) -> int:
	n = int(input())
	low = 0
	high = len(triangles) - 1
	index = (low + high) // 2
	while True:
		if triangles[index] > n:
			high = index
		elif triangles[index] < n:
			low = index
		else:
			return index
		if high - low == 1:
			return high
		index = (high + low) // 2

def diter() -> Iterator[int]:
	base = 0
	while True:
		yield from range(base, base + 3)
		base += 2
intersections = d = 0
triangles = [0]
d = diter()
while triangles[-1] < 10 ** 9:
	intersections += next(d)
	triangles.append(2 * intersections)
results = []
for _ in range(int(input())):
	results.append(str(solve(triangles)))
print('\n'.join(results))


for _ in range(int(input())):
	print(1 + int((int(input()) * 1.5) ** 0.5 - 9e-09))


from math import isqrt
for _ in range(int(input())):
	t = (int(input()) * 3 + 1) // 2
	s = isqrt(t)
	print(s + 1 if s * s < t else s)


import math as mt
n = int(input())
for i in range(n):
	k = int(input())
	print(mt.ceil((k / 6.0) ** 0.5 * 3))


for d in range(int(input())):
	print(1 + int((int(input()) * 1.5) ** 0.5 - 9e-09))


import math as m
for i in range(int(input())):
	print(m.ceil((1.5 * int(input())) ** 0.5))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = int(math.sqrt(n / 6))
	if 6 * s * s >= n:
		print(3 * s)
	elif 6 * s * s + 4 * s >= n:
		print(3 * s + 1)
	elif 6 * s * s + 8 * s + 2 >= n:
		print(3 * s + 2)
	else:
		print(3 * s + 3)


from math import sqrt

def calc(n):
	if n < 3:
		return 2
	guess = int(sqrt(n / 6))
	lines = [guess, guess, guess]
	summ = 3 * guess
	triangles = 6 * guess * guess
	i = 0
	while True:
		if triangles >= n:
			return summ
		lines[i] += 1
		summ += 1
		temp = summ - lines[i]
		triangles += 2 * temp
		i = (i + 1) % 3
t = int(input())
for _ in range(t):
	n = int(input())
	print(calc(n))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	i = int(math.sqrt(n // 6))
	if 6 * i * i == n:
		print(3 * i)
	elif (i * i + 2 * i * (i + 1)) * 2 >= n:
		print(3 * i + 1)
	elif ((i + 1) * (i + 1) + i * (i + 1) * 2) * 2 >= n:
		print(3 * i + 2)
	else:
		print(3 * i + 3)


def check(mid, n):
	x = mid // 3
	y = x
	z = x
	if mid % 3 == 1:
		z += 1
	elif mid % 3 == 2:
		z += 1
		y += 1
	if 2 * (x * y + x * z + y * z) >= n:
		return True
	return False

def lbp(n):
	left = 1
	right = int(n ** (1 / 3)) + 1
	while right - left > 1:
		mid = (right + left) // 2
		if check(mid, n):
			right = mid
		else:
			left = mid
	if check(left, n):
		return left
	return right

def main():
	n = int(input())
	x = n / 6
	x1 = x ** 0.5
	x1 *= 3
	x1 = int(x1)
	while not check(x1, n):
		x1 += 1
	print(x1)
for i in range(int(input())):
	main()