Alex is attending a Halloween party with his girlfriend, Silvia. At the party, Silvia spots the corner of an infinite chocolate bar (two dimensional, infinitely long in width and length).  

If the chocolate can be served only as 1 x 1 sized pieces and Alex can cut the chocolate bar exactly ${K}$ times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?

Input Format 

The first line contains an integer ${T}$, the number of test cases. ${T}$ lines follow.

Each line contains an integer ${K}$.  

Output Format

${T}$ lines; each line should contain an integer that denotes the maximum number of pieces that can be obtained for each test case.

Constraints

$1\leq T\leq10$

$2\leq K\leq10^{7}$

Note: Chocolate must be served in 1 x 1 sized pieces. Alex can't relocate any of the pieces, nor can he place any piece on top of another.

Sample Input #00  

4
5
6
7
8

Sample Output #00  

6
9
12
16

Explanation

The explanation below is for the first two test cases. The rest of them follow a similar logic.

For the first test-case where $K=5$, you need $3$ horizontal and $2$ vertical cuts.
 
For the second test case, where $K=6$, you need $3$ horizontal and $3$ vertical cuts.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
answers = []
for i in range(0, int(input())):
	d = int(input())
	if d % 2 == 0:
		answers += [(d / 2) ** 2]
	else:
		answers += [(d + 1) / 2 * (d - 1) / 2]
for a in answers:
	print(int(a))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print(N * N // 4)


def main():
	n = int(input())
	arrData = []
	for i in range(0, n):
		arrData.append(int(input()))
	for j in range(0, n):
		num = int(arrData[j] / 2)
		restNum = arrData[j] - num
		print(num * restNum)
main()


__author__ = 'n.st'
import math
t = int(input())
for i in range(t):
	k = int(input())
	max = 0
	k1 = math.floor(k / 2)
	n = k1 * (k - k1)
	max = n if n > max else max
	k1 = math.ceil(k / 2)
	n = k1 * (k - k1)
	max = n if n > max else max
	print(max)


import sys

def resolve(k):
	(a, b) = divmod(k, 2)
	if b == 1:
		result = a * (a + 1)
	else:
		result = a * a
	return result
n = int(sys.stdin.readline())
for i in range(n):
	k = int(sys.stdin.readline())
	print(resolve(k))


n = int(input())
for i in range(n):
	ar = int(input())
	if ar % 2 == 0:
		print(ar // 2 * ar // 2)
	else:
		print(ar // 2 * (ar - ar // 2))


T = int(input())
for test in range(T):
	K = int(input())
	half = K // 2
	if K % 2 == 0:
		print(half * half)
	else:
		print(half * (half + 1))


T = int(input())
ks = []
for x in range(0, T):
	k = int(input())
	ks.append(k)
for y in ks:
	num = y // 2
	if y % 2 == 0:
		print(num * num)
	else:
		print(num * (num + 1))


t = int(input())
for i in range(t):
	n = int(input())
	column = n // 2
	row = n - column
	print(column * row)


import math
t = int(input())
if t >= 1 and t <= 10:
	i = 1
	lis = []
	ans = []
	while i < 10 ** 7:
		if i <= t:
			k = int(input())
			lis.append(k)
			i += 1
		else:
			break
for i in range(0, t):
	b = int(lis[i])
	if b % 2 == 0:
		c = int(b / 2)
		ans.append(c * c)
	else:
		c = math.floor(b / 2)
		d = c + 1
		ans.append(c * d)
for i in range(0, t):
	print(ans[i])


t = 1
b = []
T = int(input(''))
while t <= T:
	K = input('')
	b.append(K)
	t += 1
a = []
for dg in b:
	y = int(dg)
	if y < 1 or y > 10 ** 7:
		break
if len(b) != T:
	exit
elif T < 1 or T > 10:
	exit
else:
	for dg in b:
		y = int(dg)
		if y == 0:
			print(0)
		elif y % 2 == 0:
			print((y // 2) ** 2)
		else:
			y = y + 1
			n = y // 2
			print(n * (n - 1))


def s(y):
	if y % 2 == 1:
		mas = int(y / 2) * (int(y / 2) + 1)
	else:
		mas = int(y / 2) * int(y / 2)
	print(mas)
m = int(input())
for i in range(0, m):
	s(int(input().strip()))


n = int(input())
for i in range(n):
	k = int(input())
	m = k // 2
	n = k - m
	print(m * n)


testcase = int(input())
for x in range(testcase):
	num = int(input())
	if num % 2 == 0:
		print(int((num / 2) ** 2))
	else:
		other = num - (num + 1) / 2
		print(int(other * ((num + 1) / 2)))


def chocolate(K):
	if K % 2 == 0:
		m = K / 2
		return m ** 2
	else:
		m = int(K / 2)
		n = int(K / 2) + 1
		return m * n

def main():
	T = int(input())
	for i in range(T):
		K = int(input())
		print(int(chocolate(K)))
	return 0
main()


for i in range(int(input())):
	n = int(input())
	print(n // 2 * (n // 2 + n % 2))


lines = int(input())
inputs = [int(input()) for _ in range(lines)]
for case in inputs:
	half = case // 2
	print(half * (case - half))


t = int(input())
for i in range(0, t):
	k = int(input())
	w = int(k / 2) + k % 2
	h = int(k / 2)
	pieces = w * h
	print(pieces)


import sys
input = list(sys.stdin)
for line in input[1:]:
	k = int(line)
	m = k // 2
	d = k - m
	print(m * d)


N = int(input())
res = list()
for i in range(N):
	K = int(input())
	if K % 2 == 0:
		res.append((K / 2) ** 2)
	else:
		res.append(K // 2 * (K // 2 + 1))
for el in res:
	print(int(el))


T = int(input())
for i in range(T):
	K = int(input())
	x = K / 2
	y = K - x
	print(int(x * y))


t = int(input())
for i in range(0, t):
	k = int(input())
	w = int(k / 2) + k % 2
	h = int(k / 2)
	pieces = w * h
	print(pieces)


t = int(input())
for _ in range(t):
	k = int(input())
	x = (k + 1) // 2
	y = k - x
	print(x * y)


def fun():
	r = input()
	r1 = int(r)
	for i in range(r1):
		ip = input()
		ip1 = int(ip)
		ip2 = int(ip1 / 2) + ip1 % 2
		s = ip2 * (ip1 - ip2)
		print(s)
fun()


caseCnt = int(input())
for caseNr in range(caseCnt):
	n = int(input())
	k = int(n / 2)
	print(k * (n - k))


import fileinput
r = fileinput.input()
count = int(r.readline())
while count > 0:
	k = int(r.readline())
	w = int(k / 2)
	h = k - w
	print(w * h)
	count -= 1
r.close()


T = int(input())
for t in range(T):
	K = int(input())
	h = K // 2
	v = K - h
	print(h * v)


T = int(input())
for i in range(T):
	n = int(input())
	hn = n // 2
	print(hn * (n - hn))


t = int(input())
while t:
	t -= 1
	n = int(input())
	print(n // 2 * (n // 2 + n % 2))


import sys
numtests = int(sys.stdin.readline())
tests = []
for i in range(numtests):
	tests.append(int(sys.stdin.readline()))
for i in range(numtests):
	k = tests[i]
	if not k % 2:
		print(k // 2 * (k // 2))
	else:
		print((k - 1) // 2 * ((k - 1) // 2 + 1))


T = int(input())
L = []
for x in range(0, T):
	R = int(input())
	L.append(R)
An = []
for r in L:
	if r % 2 == 0:
		An.append(r // 2 * r // 2)
	else:
		An.append(r // 2 * (r // 2 + 1))
for x in An:
	print(x)


T = int(input())
for t in range(0, T):
	K = int(input())
	print(K // 2 * (K - K // 2))


from math import ceil
ks = []
pieces = []
for i in range(int(input())):
	ks.append(int(input()))
for k in ks:
	if k % 2 == 0:
		pieces.append(int(pow(k / 2, 2)))
	else:
		pieces.append(ceil(k / 2) * (ceil(k / 2) - 1))
for piece in pieces:
	print(piece)


T = int(input())
while T > 0:
	K = int(input())
	print(K // 2 * (K - K // 2))
	T -= 1


T = int(input())
for case in range(T):
	K = int(input())
	print(K // 2 * (K - K // 2))


tcs = int(input())
results = list()
for tc_i in range(tcs):
	k = int(input())
	a = int(k / 2)
	b = a + k % 2
	results.append(a * b)
for r in results:
	print(r)


import sys

def max_pieces(n):
	return n // 2 * (n - n // 2)

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		print(max_pieces(int(sys.stdin.readline())))
main()


t = int(input())

def pieces(k):
	return (k * k - k % 2) // 4
for _ in range(t):
	print(pieces(int(input())))


testcase = int(input())
for i in range(1, testcase + 1):
	k = int(input())
	half = int(k / 2)
	half2 = k - half
	total = half * half2
	print(total)


scan = lambda : int(input())
t = scan()
for i in range(t):
	a = scan()
	print((a // 2) ** 2 + a * (a % 2) // 2)


def chocolate(cuts):
	return cuts // 2 * (cuts - cuts // 2)
T = int(input())
N = [int(input()) for _ in range(T)]
for n in N:
	print(chocolate(n))


testcases = int(input())
numcuts = []
for i in range(testcases):
	nc = int(input())
	numcuts.append(nc)

def chocolates(cuts):
	for i in numcuts:
		if i % 2 == 0:
			print(int((i / 2) ** 2))
		else:
			print(int(i // 2 * (i - i // 2)))
chocolates(numcuts)


import sys
T = int(sys.stdin.readline())
for case in range(T):
	K = int(sys.stdin.readline())
	x = K // 2
	print(x * (x + K % 2))


import sys
import math

def max_chocs(cuts):
	h_cuts = math.ceil(cuts / 2)
	v_cuts = cuts - h_cuts
	print(h_cuts * v_cuts)
T = int(sys.stdin.readline())
testcases_list = []
for t in range(T):
	testcases_list.append(int(sys.stdin.readline()))
for testcase in testcases_list:
	max_chocs(testcase)


t = int(input())
c = 0
while t > c:
	g = int(input())
	if g % 2 == 0:
		print(int(g / 2) ** 2)
	else:
		print(int(((g + 1) / 2) ** 2 - (g + 1) / 2))
	c += 1


import sys
import math
f = sys.stdin
size = int(f.readline())
i = 0
while i < size:
	val = int(f.readline())
	ret1 = int(val / 2)
	ret2 = val - ret1
	print(ret1 * ret2)
	i += 1


N = int(input())
z = []
for i in range(0, N):
	K = int(input())
	if K % 2 == 0:
		z += [(K / 2) ** 2]
	else:
		z += [(K + 1) / 2 * (K - 1) / 2]
for z1 in z:
	print(int(z1))


t = int(input())
for i in range(t):
	k = int(input())
	l = int(k / 2)
	b = k - l
	print(l * b)


from math import ceil
T = int(input())
for i in range(T):
	k = int(input())
	h = ceil(k / 2)
	v = k - h
	print(h * v)


import sys
import math

def main():
	for (i, line) in enumerate(sys.stdin):
		if i == 0:
			pass
		else:
			calculatepieces(int(line))

def calculatepieces(integer):
	if integer % 2 == 0:
		a = int((integer / 2) ** 2)
		print(a)
	else:
		b = int(round(math.floor(integer / 2)))
		c = b + 1
		d = b * c
		print(d)
main()


T = int(input())
for i in range(T):
	k = int(input())
	if k % 2 == 0:
		ans = int(k / 2 * (k / 2))
	elif k % 2 == 1:
		ans = int(k / 2) * (int(k / 2) + 1)
	print(ans)


from math import *
T = int(input())
for i in range(T):
	K = int(input())
	V = K
	while V / 2 % 1 != 0:
		V = V - 1
	V = V / 2
	H = K - V
	print(int(H * V))


T = eval(input())
for k in range(T):
	max = 0
	K = eval(input())
	if K % 2 == 0:
		print(K // 2 * K // 2)
	else:
		print(K // 2 * (K // 2 + 1))


import sys
T = int(sys.stdin.readline())
list = []
for i in range(T):
	list.append(int(sys.stdin.readline()))
for item in list:
	print(int(item / 2) * (int(item / 2) + item % 2))


tests = int(input())
for i in range(tests):
	k = int(input())
	if k % 2 == 0:
		z = int(k / 2)
		print(z ** 2)
	else:
		z = k // 2
		print(z * (z + 1))


t = int(input())
k = []
for i in range(t):
	k.append(int(input()))
for i in k:
	if i % 2 == 0:
		print(int(i / 2) * int(i / 2))
	else:
		print(int(i / 2) * (int(i / 2) + 1))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	K = int(sys.stdin.readline())
	print(K // 2 * (K - K // 2))


t = int(input())
for i in range(t):
	lines = int(input())
	h = lines // 2
	v = lines - h
	print(h * v)


import sys
lines = []
for line in sys.stdin:
	lines.append(line)
T = int(lines[0])
Ks = lines[1:]
for i in range(T):
	Ks[i] = int(Ks[i])
for K in Ks:
	if K % 2 == 0:
		print(int(K / 2 * (K / 2)))
	else:
		print(int((K - 1) / 2 * (K + 1) / 2))


t = int(input())
while t > 0:
	t -= 1
	k = int(input())
	k_ = k // 2
	print((k - k_) * k_)


cases = int(input())
i = 1
stri = ''
while i <= cases:
	k = int(input())
	pieces = 0
	if k % 2 == 0:
		pieces = (k / 2) ** 2
	else:
		pieces = ((k - 1) / 2) ** 2 + (k - 1) / 2
	if i != cases:
		stri = stri + str(int(pieces)) + '\n'
	else:
		stri = stri + str(int(pieces))
	i += 1
print(stri)


import math
import sys
line = sys.stdin.readline().strip()
t = int(line)
for i in range(0, t):
	k = int(sys.stdin.readline().strip())
	x = k // 2
	y = k // 2
	if k % 2:
		y += 1
	print(x * y)


t = int(input())
for i in range(0, t):
	k = int(input())
	floor = int(k / 2)
	res = 0
	if k % 2 == 0:
		res = floor * floor
	else:
		res = floor * (floor + 1)
	print(res)


T = int(input())
for i in range(T):
	K = int(input())
	if K % 2 == 0:
		print((K // 2) ** 2)
	else:
		print(K // 2 * (K // 2 + 1))


for i in range(int(input())):
	x = int(input())
	if x % 2 == 0:
		print(int(x ** 2 / 4))
	else:
		print(int((x ** 2 - 1) / 4))


from sys import stdin
t = int(stdin.readline())
for i in range(t):
	k = int(stdin.readline())
	a = k // 2
	b = k - a
	print(a * b)


def main():
	n = int(input())
	for i in range(n):
		x = int(input())
		if x % 2 == 0:
			print((x // 2) ** 2)
		else:
			a = x // 2
			b = a + 1
			print(a * b)
main()


T = int(input())
for i in range(T):
	K = int(input())
	x = K // 2
	y = K - x
	print(x * y)


t = int(input())

def solve(k):
	if k == 1:
		print(2)
	elif k == 2:
		print(4)
	elif k == 3:
		print(6)
	elif k == 4:
		print(9)
	elif k % 2 == 1:
		n = (k + 1) / 2
		print(int((n - 1) * n))
	elif k % 2 == 0:
		print(int((k / 2) ** 2))
for test in range(t):
	k = int(input())
	solve(k)


def check(x):
	if x == 0:
		return 0
	elif x % 2 == 0:
		return (x / 2) ** 2
	elif x % 2 != 0:
		return int(x / 2) * (int(x / 2) + 1)
t = int(input())
list = []
while t > 0:
	n = int(input())
	list.append(check(n))
	t -= 1
for entry in list:
	print(int(entry))


def number_of_pieces(k):
	h = int(k / 2)
	return h * (k - h)
T = int(input().strip())
K = [int(input().strip()) for i in range(T)]
for k in K:
	print(number_of_pieces(k))


T = int(input())
for i in range(T):
	K = int(input())
	H = int(K / 2)
	V = K - H
	print(H * V)


t = int(input())
for i in range(t):
	j = int(input())
	if j % 2 == 0:
		a = int(j / 2)
		a *= a
	else:
		a = int((j + 1) / 2)
		b = j - a
		a *= b
	print(a)


import sys
lines = [int(l.replace('\n', '')) for l in sys.stdin.readlines()][1:]
for l in lines:
	h = l // 2
	print(h ** 2 if l % 2 == 0 else h * (h + 1))


from sys import stdin
T = int(stdin.readline())
for t in range(T):
	N = int(stdin.readline())
	h = N // 2
	print(h * (N - h))


numTests = int(input())
cuts = []
for t in range(0, numTests):
	cuts.append(int(input()))
for k in cuts:
	print((k - k // 2) * (k // 2))


T = int(input())
for i in range(0, T):
	K = int(input())
	if K == 1:
		ans = 2
	elif K == 2:
		ans = 3
	elif K == 3:
		ans = 4
	n1 = int(K / 2)
	n2 = K - n1
	ans = n1 * n2
	print(ans)


t = int(input())
for _ in range(t):
	k = int(input())
	h = int(round(k / 2))
	v = k - h
	print(h * v)


T = int(input())
for i in range(T):
	K = int(input())
	print(K * K // 4)


import math
numberCases = int(input())
for i in range(0, numberCases):
	size = int(input())
	print(int(math.pow(size / 2, 2)))


import sys
data = sys.stdin.readlines()
for n in data[1:]:
	num = int(n)
	if num % 2 == 0:
		result = int(num / 2 * (num / 2))
		print(result)
	else:
		x = num / 2
		result = int(x * (num - x))
		print(result)


tc = int(input())
for c in range(tc):
	n = int(input())
	print((int(n / 2) + n % 2) * int(n / 2))


def num_cuts(K):
	return int(K / 2) * int((K + 1) / 2)
num_cases = int(input())
for i in range(num_cases):
	print(num_cuts(int(input())))


for bita3 in range(int(input())):
	x = int(input())
	if x % 2 == 0:
		print(int(x * x / 4))
	else:
		print(int(x / 2) * (int(x / 2) + 1))


test = eval(input())
for i in range(test):
	a = eval(input())
	if a == 1:
		print(2)
	elif a % 2 == 1:
		a //= 2
		print(a * (a + 1))
	else:
		a //= 2
		print(a * a)


def isEven(n):
	return n % 2 == 0

def main():
	times = int(input())
	cuts = []
	for i in range(times):
		cuts.append(int(input()))
	for i in range(times):
		if not isEven(cuts[i]):
			pieces = (cuts[i] // 2 + 1) * (cuts[i] // 2)
		elif isEven(cuts[i]):
			pieces = (cuts[i] // 2) ** 2
		print(pieces)
main()


T = int(input())
for t in range(T):
	K = int(input())
	result = (K // 2) ** 2 + K // 2 * (K % 2)
	print(result)


nInputs = input()
for x in range(0, int(nInputs)):
	a = input()
	b = int(a) // 2
	c = (int(a) - b) * b
	print(c)


T = int(input())
for i in range(0, T):
	K = int(input())
	if K / 2 == round(K / 2):
		print(int(K * K / 4))
	else:
		print(int((K * K - 1) / 4))


for i in range(int(input())):
	(a, b) = divmod(int(input()), 2)
	print(a * (a + b))


for t in range(int(input())):
	n = int(input())
	print(n // 2 * (n - n // 2))


from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	K = int(stdin.readline())
	vert = K // 2
	horiz = K - vert
	print(vert * horiz)


tests = int(input())
for test in range(tests):
	cuts = int(input())
	hor = cuts // 2
	vert = hor + cuts % 2
	print(hor * vert)


t = int(input())
for i in range(t):
	j = int(input())
	if j % 2 == 0:
		print((j // 2) ** 2)
	else:
		print(j // 2 * (j // 2 + 1))


t = int(input())
n = []
for i in range(t):
	q = int(input())
	n.append(q)
for i in range(len(n)):
	m = int(n[i])
	if m % 2 == 1:
		print(int((m + 1) / 2 * (m - 1) / 2))
	else:
		print(int((m / 2) ** 2))


def cut(max_cuts):
	cut_row = max_cuts / 2
	cut_col = max_cuts - cut_row
	return int(cut_row * cut_col)
tests = int(input())
for i in range(tests):
	print(cut(int(input())))