A string is made of only lowercase latin letters (a,b,c,d,.....,z). Can you find the length of the lexicographically smallest string such that it has exactly ${K}$ sub-strings, each of which are palindromes? 

Input Format

The first line of input contains single integer ${T}$ - the number of testcases. 

T lines follow, each containing the integer ${K}$.

Constraints

$1\leq T\leq100$  
$1\leq K\leq10^{12}$  

Output Format

Output exactly ${T}$ lines. Each line should contain single integer - the length of the lexicographically smallest string.

Sample Input
2
10
17

Sample Output
4
7

Explanation

for $K=10$, one of the smallest possible strings that satisfies the property is aaaa. 
All $10$ palindromes are 

a,a,a,a 
aa, aa, aa
aaa, aaa
aaaa

Note

Two sub-strings with different indices are both counted.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Combinatorics


Solutions:
def compute_pallindrome_length(n):
	length = 0
	debug_print = False
	current_n = 0
	if n == 5:
		return 4
	elif n == 8:
		return 5
	i = int((1 + pow(1 + 8 * n, 0.5)) / 2) - 10
	while i * (i + 1) // 2 <= n:
		current_n = i
		i += 1
	length += current_n
	n -= current_n * (current_n + 1) // 2
	if debug_print:
		print('first step', current_n, length, n)
	num_b = 0
	if n != 0 and n >= 9:
		i = max(0, int(-3 + int(pow(9 + 8 * (n - 1), 0.5))) // 2 - 10)
		current_n = i
		while i * (i + 1) // 2 + i + 1 <= n:
			current_n = i
			i += 1
		length += current_n + 1
		n -= current_n * (current_n + 1) // 2 + current_n + 1
		num_b += 1
		if debug_print:
			print('second step', current_n, length, n)
	while n >= 9:
		i = 0
		current_n = 0
		while i * (i + 1) // 2 + 2 * i + 2 <= n:
			current_n = i
			i += 1
		length += current_n + 1
		n -= current_n * (current_n + 1) // 2 + 2 * current_n + 2
		num_b += 1
		if debug_print:
			print('next step', current_n, length, n)
	if debug_print:
		print('remainder ', n)
	if n == 1:
		length += 1
	elif n == 2 and num_b > 0:
		length += 1
	elif n == 2 and num_b == 0:
		length += 2
	elif n == 3:
		length += 2
	elif n == 4 and num_b >= 1:
		length += 2
	elif n == 4 and num_b == 0:
		length += 3
	elif n == 5 and num_b >= 1:
		length += 2
	elif n == 5 and num_b == 0:
		length += 3
	elif n == 6:
		length += 3
	elif n == 7 and num_b > 0:
		length += 3
	elif n == 7 and num_b == 0:
		length += 4
	elif n == 8 and num_b > 0:
		length += 4
	elif n == 8 and num_b == 0:
		length += 4
	return length
T = int(input())
for _ in range(0, T):
	n = int(input())
	print(compute_pallindrome_length(n))


def compute_pallindrome_length(n):
	length = 0
	debug_print = False
	current_n = 0
	if n == 5:
		return 4
	elif n == 8:
		return 5
	i = int((1 + pow(1 + 8 * n, 0.5)) / 2) - 10
	while i * (i + 1) // 2 <= n:
		current_n = i
		i += 1
	length += current_n
	n -= current_n * (current_n + 1) // 2
	if debug_print:
		print('first step', current_n, length, n)
	num_b = 0
	if n != 0 and n >= 9:
		i = max(0, int(-3 + int(pow(9 + 8 * (n - 1), 0.5))) // 2 - 10)
		current_n = i
		while i * (i + 1) // 2 + i + 1 <= n:
			current_n = i
			i += 1
		length += current_n + 1
		n -= current_n * (current_n + 1) // 2 + current_n + 1
		num_b += 1
		if debug_print:
			print('second step', current_n, length, n)
	while n >= 9:
		i = 0
		current_n = 0
		while i * (i + 1) // 2 + 2 * i + 2 <= n:
			current_n = i
			i += 1
		length += current_n + 1
		n -= current_n * (current_n + 1) // 2 + 2 * current_n + 2
		num_b += 1
		if debug_print:
			print('next step', current_n, length, n)
	if debug_print:
		print('remainder ', n)
	if n == 1:
		length += 1
	elif n == 2 and num_b > 0:
		length += 1
	elif n == 2 and num_b == 0:
		length += 2
	elif n == 3:
		length += 2
	elif n == 4 and num_b >= 1:
		length += 2
	elif n == 4 and num_b == 0:
		length += 3
	elif n == 5 and num_b >= 1:
		length += 2
	elif n == 5 and num_b == 0:
		length += 3
	elif n == 6:
		length += 3
	elif n == 7 and num_b > 0:
		length += 3
	elif n == 7 and num_b == 0:
		length += 4
	elif n == 8 and num_b > 0:
		length += 4
	elif n == 8 and num_b == 0:
		length += 4
	return length
T = int(input())
for _ in range(0, T):
	n = int(input())
	print(compute_pallindrome_length(n))


def compute_pallindrome_length(n):
	length = 0
	debug_print = False
	current_n = 0
	if n == 5:
		return 4
	elif n == 8:
		return 5
	i = int((1 + pow(1 + 8 * n, 0.5)) / 2) - 10
	while i * (i + 1) // 2 <= n:
		current_n = i
		i += 1
	length += current_n
	n -= current_n * (current_n + 1) // 2
	if debug_print:
		print('first step', current_n, length, n)
	num_b = 0
	if n != 0 and n >= 9:
		i = max(0, int(-3 + int(pow(9 + 8 * (n - 1), 0.5))) // 2 - 10)
		current_n = i
		while i * (i + 1) // 2 + i + 1 <= n:
			current_n = i
			i += 1
		length += current_n + 1
		n -= current_n * (current_n + 1) // 2 + current_n + 1
		num_b += 1
		if debug_print:
			print('second step', current_n, length, n)
	while n >= 9:
		i = 0
		current_n = 0
		while i * (i + 1) // 2 + 2 * i + 2 <= n:
			current_n = i
			i += 1
		length += current_n + 1
		n -= current_n * (current_n + 1) // 2 + 2 * current_n + 2
		num_b += 1
		if debug_print:
			print('next step', current_n, length, n)
	if debug_print:
		print('remainder ', n)
	if n == 1:
		length += 1
	elif n == 2 and num_b > 0:
		length += 1
	elif n == 2 and num_b == 0:
		length += 2
	elif n == 3:
		length += 2
	elif n == 4 and num_b >= 1:
		length += 2
	elif n == 4 and num_b == 0:
		length += 3
	elif n == 5 and num_b >= 1:
		length += 2
	elif n == 5 and num_b == 0:
		length += 3
	elif n == 6:
		length += 3
	elif n == 7 and num_b > 0:
		length += 3
	elif n == 7 and num_b == 0:
		length += 4
	elif n == 8 and num_b > 0:
		length += 4
	elif n == 8 and num_b == 0:
		length += 4
	return length
T = int(input())
for _ in range(0, T):
	n = int(input())
	print(compute_pallindrome_length(n))