Our unsung tower-breaking heroes (players $\mathbf{P_1}$ and $P_2$) only have one tower left, and they've decided to break it for a special game commemorating the end of $5$ days of Game Theory! The rules are as follows:

$\mathbf{P_1}$ always moves first, and both players always move optimally.
Initially there is $\mbox{1}$ tower of height $N$.
The players move in alternating turns. The moves performed by each player are different:
At each turn, $\mathbf{P_1}$ divides the current tower into some number of smaller towers. If the turn starts with a tower of height $\mbox{H}$ and $\mathbf{P_1}$ breaks it into $x\geq2$ smaller towers, the following condition must apply: $H=h_1+h_2+...+h_x$, where $h_i$ denotes the height of the $i^{\mbox{th}}$ new tower.
At each turn, $P_2$ chooses some tower $\boldsymbol{\mbox{k}}$ of the $\boldsymbol{x}$ new towers made by $\mathbf{P_1}$ (where $1\leq k\leq x$). Then $\mathbf{P_1}$ must pay $k^2$ coins to $P_2$. After that, $\mathbf{P_1}$ gets another turn with tower $h_{k}$ and the game continues.
The game is over when no valid move can be made by $\mathbf{P_1}$, meaning that $H=1$.
$\mathbf{P_1}$'s goal is to pay as few coins as possible, and $P_2$'s goal is to earn as many coins as possible. 

Can you predict the number of coins that $P_2$ will earn?

Input Format

The first line contains a single integer, $\mathbf{T}$, denoting the number of test cases. 

Each of the $\mathbf{T}$ subsequent lines contains a single integer, $N$, defining the initial tower height for a test case.

Constraints

$1\leq T\leq100$
$2\leq N\leq10^{18}$

Output Format

For each test case, print a single integer denoting the number of coins earned by $P_2$ on a new line.

Sample Input
3
4
2
7

Sample Output
6
4
8

Explanation

Test Case 0: 

Our players make the following moves:

$H=N=4$
$\mathbf{P_1}$ splits the initial tower into $2$ smaller towers of sizes $3$ and $\mbox{1}$. 
$P_2$ chooses the first tower and earns $1^2=1$ coin. 
$H=3$
$\mathbf{P_1}$ splits the tower into $2$ smaller towers of sizes $2$ and $\mbox{1}$. 
$P_2$ chooses the first tower and earns $1^2=1$ coin.
$H=2$
$\mathbf{P_1}$ splits the tower into $2$ smaller towers of size $\mbox{1}$. 
$P_2$ chooses the second tower and earns $2^2=4$ coins.

The total number of coins earned by $P_2$ is $1+1+4=6$, so we print $\boldsymbol{6}$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Game theory


Solutions:
largest = 1000000000000000000
T = int(input())
height = [0] * 1000
height[0] = 1
for i in range(1, 261):
	for j in range(1, int(i ** 0.5) + 1):
		height[i] += height[i - j * j]
		if height[i] > largest:
			break
while T > 0:
	n = int(input())
	for i in range(261):
		if height[i] >= n:
			print(i)
			break
		i += 1
	T -= 1


def getInd(freq, n):
	acc = 0
	for i in range(len(freq)):
		acc += freq[i]
		if n <= acc:
			return i
n = 10 ** 18
freq = [1, 0, 0, 0, 1] + [0] * 120
part = [1, 1]
a = 3
while a <= n:
	min_val = 10 ** 10
	for (i, p) in enumerate(part + [0]):
		coins = getInd(freq, p + 1)
		val = coins + (i + 1) ** 2
		if val < min_val:
			min_val = val
			next_i = i
			similar_coins = freq[coins]
	if next_i < len(part):
		part[next_i] += similar_coins
	else:
		part += [1]
	freq[min_val] += similar_coins
	a += similar_coins
for _ in range(int(input())):
	print(getInd(freq, int(input())))


def solve(n, cache={}):
	if n == 0:
		return 1
	if n in cache:
		return cache[n]
	sqrtN = int(n ** 0.5)
	cache[n] = sum((solve(n - i * i) for i in range(1, sqrtN + 1)))
	return cache[n]
for t in range(int(input())):
	N = int(input())
	n = 1
	while solve(n) < N:
		n += 1
	print(n)


import math

def tower_to_gold(num):
	split_time = int(math.sqrt(num))
	k_2 = []
	h_2 = [0] * split_time
	v_2 = []
	for n in range(split_time):
		k_2.append((n + 1) ** 2)
		gold_in_dict = num - (n + 1) ** 2
		if gold_in_dict in gold_dict.keys():
			h_2[n] = gold_in_dict
	for h in h_2:
		v_2.append(gold_dict[h])
	gold_dict[num] = sum(v_2)

def check_values(num):
	for n in range(300):
		if num <= gold_num_list[n]:
			return n
gold_dict = {0: 1, 4: 2, 5: 3, 6: 4, 7: 5, 8: 7}
for n in range(9, 200):
	tower_to_gold(n)
tower_num_list = list(gold_dict.keys())
gold_num_list = list(gold_dict.values())
nums = int(input())
result_list = []
for x in range(nums):
	temp_input = int(input())
	result_list.append(tower_num_list[check_values(temp_input)])
for r in result_list:
	print(r)


from bisect import bisect_left
from itertools import count, takewhile
MAX = 10 ** 18
dp = [1]
while dp[-1] < MAX:
	squares = (x * x for x in count(1))
	dp.append(sum((dp[-i] for i in takewhile(lambda x: x <= len(dp), squares))))
for _ in range(int(input())):
	print(bisect_left(dp, int(input())))


from math import *

class Calculator:

	def __init__(self):
		self.storedResults = {}

	def findTowersPerGain(self, n):
		if n in self.storedResults:
			return self.storedResults.get(n)
		if n == 0:
			self.storedResults[n] = 1
			return 1
		if n == 1 or n == 2 or n == 3:
			self.storedResults[n] = 0
			return 0
		if n == 4:
			self.storedResults[n] = 1
			return 1
		lim = floor(sqrt(n))
		res = 0
		for i in range(1, lim + 1):
			res += self.findTowersPerGain(n - i ** 2)
		self.storedResults[n] = res
		return res

	def findGain(self, n):
		sum = 0
		gain = -1
		while sum < n:
			gain += 1
			sum += self.findTowersPerGain(gain)
		return gain
T = int(input())
calc = Calculator()
for i in range(T):
	N = int(input())
	res = calc.findGain(N)
	print(res)


arr = [1]
l = 1
while arr[-1] < 10 ** 18 + 1:
	i = 1
	j = 1
	g = 0
	while j <= l:
		g += arr[-j]
		i += 1
		j = i ** 2
	l += 1
	arr.append(g)
for i in range(int(input())):
	n = int(input())
	a = [x for x in arr if x < n]
	print(len(a))


import fileinput
from collections import defaultdict
gdict = defaultdict(int)
vdict = []
gdict[0] = 1
gdict[1] = 1
gdict[2] = 1
gdict[3] = 1
vdict.append([1, 0])

def getLoss(n):
	max_e = 0
	for vp in vdict:
		if n >= vp[0]:
			max_e = vp[1]
		else:
			break
	return max_e

def getAbsLoss(n):
	max_e = 0
	for vp in vdict:
		max_e = vp[0]
		if n <= vp[1]:
			break
	return max_e

def getVal(n):
	if n - 1 not in gdict:
		raise 'getVal called for {} while {} is not ready'.format(n, n - 1)
	i = 1
	sum_e = 0
	max_e = 0
	tup_e = []
	while n >= i * i:
		sum_e += gdict[n - i * i]
		max_e = max(max_e, i * i + getLoss(gdict[n - i * i]))
		tup_e.append(gdict[n - i * i])
		i += 1
	gdict[n] = sum_e
	vdict.append([n, sum_e])
for i in range(4, 122):
	getVal(i)
with fileinput.input() as f:
	T = int(f.readline())
	for i in range(T):
		n = int(f.readline())
		print(getAbsLoss(n))


import math as m
import sys
mx = sys.maxsize
l = [1]
n = int(input())
for _ in range(1, 260):
	l.append(0)
	for __ in range(1, int(m.sqrt(_)) + 1):
		l[_] = l[_] + l[_ - __ * __]
		if l[_] > mx:
			break
for _ in range(n):
	k = int(input())
	for _ in range(1, 260):
		if l[_] >= k:
			print(_)
			break


big = int(1e+18)
dp = [0 for i in range(261)]
dp[0] = 1
for i in range(1, 261):
	for j in range(1, int(i ** 0.5 + 0.001) + 1):
		dp[i] += dp[i - j * j]
		if dp[i] > big:
			break
t = int(input())
for _ in range(t):
	n = int(input())
	for i in range(1, 261):
		if dp[i] >= n:
			print(i)
			break


from bisect import bisect
(rs, E) = ([0] * 301, 10 ** 18)
rs[0] = 1
for i in range(1, 301):
	(jr, j) = (i ** 0.5, 1)
	while rs[i] <= E and j <= jr:
		rs[i] += rs[i - j * j]
		j += 1
for _ in range(int(input())):
	print(bisect(rs, int(input()) - 0.5))


import sys
from time import time
import bisect

def count_gen():
	ccache = [0, 1, 2]
	vcache = [0, 0, 4]
	for (c, v) in zip(ccache, vcache):
		yield (c, v)
	while True:
		(target, total) = (vcache[-1] + 1, 0)
		r = int(pow(target, 0.5))
		for i in range(r, 0, -1):
			v = target - i * i
			index = bisect.bisect_right(vcache, v)
			c = ccache[index - 1]
			total += c
		(c, v) = (total, vcache[-1] + 1)
		ccache.append(c)
		vcache.append(v)
		yield (c, v)

def get_cache(n):
	print('n=%d' % n, file=sys.stderr)
	(ccache, vcache) = ([], [])
	for (c, v) in count_gen():
		print('\tc=%d v=%d' % (c, v), file=sys.stderr)
		ccache.append(c)
		vcache.append(v)
		if c >= n:
			break
	return (ccache, vcache)

def solve(n, ccache, vcache):
	print('n=%d' % n, file=sys.stderr)
	index = bisect.bisect_left(ccache, n)
	return vcache[index]
tm = time()
N = pow(10, 18)
(ccache, vcache) = get_cache(N)
print('cache generated', file=sys.stderr)
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n, ccache, vcache))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import sys
import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict
d = defaultdict(int)
d[0] = 1

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	for i in range(1, 130):
		d[i] = F(i)
	while d[ans] < n:
		ans += 1
	print(ans)
for i in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import os
import sys
import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


from bisect import bisect_left
a = [1]
N = 10 ** 20
while a[-1] < N:
	n = len(a)
	a.append(sum((a[n - i * i] for i in range(1, int(2 + n ** 0.5)) if i * i <= n)))
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


largest = 1000000000000000000
T = int(input())
height = [0] * 1000
height[0] = 1
for i in range(1, 261):
	for j in range(1, int(i ** 0.5) + 1):
		height[i] += height[i - j * j]
		if height[i] > largest:
			break
while T > 0:
	n = int(input())
	for i in range(261):
		if height[i] >= n:
			print(i)
			break
		i += 1
	T -= 1


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


largest = 1000000000000000000
T = int(input())
height = [0] * 1000
height[0] = 1
for i in range(1, 261):
	for j in range(1, int(i ** 0.5) + 1):
		height[i] += height[i - j * j]
		if height[i] > largest:
			break
while T > 0:
	n = int(input())
	for i in range(261):
		if height[i] >= n:
			print(i)
			break
		i += 1
	T -= 1


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import os
import sys
import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


from bisect import bisect_left

def part(high):
	a = [0] * (1 + high)
	a[0] = 1
	for n in range(1, 1 + high):
		k = 1
		while k * k <= n:
			a[n] += a[n - k * k]
			k += 1
	return a
a = part(121)
for _ in range(int(input())):
	print(bisect_left(a, int(input())))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


V = [1, 1, 1, 1, 2]
p = [1, 4]
cnt = 3
val = 5
while True:
	ans = 0
	for s in p:
		ans += V[val - s]
	V.append(ans)
	if ans > 10 ** 18:
		V.append(2 * ans)
		break
	val += 1
	if cnt ** 2 == val:
		p.append(val)
		cnt += 1
T = int(input())
for _ in range(T):
	N = int(input())
	for i in range(len(V)):
		if V[i] < N <= V[i + 1]:
			print(i + 1)
			break


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))


import math
from collections import defaultdict

def F(n):
	if n in d:
		return d[n]
	else:
		temp = 0
		for k in range(1, int(math.sqrt(n)) + 1):
			temp += F(n - k ** 2)
		d[n] = temp
		return d[n]

def towerBreakers(n):
	ans = 0
	while d[ans] < n:
		ans += 1
	print(ans)
d = defaultdict(int)
d[0] = 1
F(130)
for _ in range(int(input())):
	towerBreakers(int(input()))