Now that Chef has finished baking and frosting his cupcakes, it's time to package them. Chef has N cupcakes, and needs to decide how many cupcakes to place in each package. Each package must contain the same number of cupcakes. Chef will choose an integer A between 1 and N, inclusive, and place exactly A cupcakes into each package.  Chef makes as many packages as possible. Chef then gets to eat the remaining cupcakes. Chef enjoys eating cupcakes very much. Help Chef choose the package size A that will let him eat as many cupcakes as possible.

-----Input-----

Input begins with an integer T, the number of test cases. Each test case consists of a single integer N, the number of cupcakes.

-----Output-----

For each test case, output the package size that will maximize the number of leftover cupcakes. If multiple package sizes will result in the same number of leftover cupcakes, print the largest such size.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 2 ≤ N ≤ 100000000 (108)

-----Sample Input-----
2
2
5

-----Sample Output-----
2
3

-----Explanation-----

In the first test case, there will be no leftover cupcakes regardless of the size Chef chooses, so he chooses the largest possible size.  In the second test case, there will be 2 leftover cupcakes.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	print(n // 2 + 1)


import math
t = int(input())
for i in range(t):
	x = int(input())
	y = int(math.floor(x / 2 + 1))
	print(y)


for _ in range(int(input())):
	n = int(input())
	print(n // 2 + 1)


t = int(input())
for i in range(0, t):
	n = int(input())
	if n == 2:
		print(n)
	else:
		print(n // 2 + 1)


s = int(input())
for i in range(s):
	t = int(input())
	print(t // 2 + 1)


T = int(input())
for i in range(T):
	n = int(input())
	print(n // 2 + 1)


t = int(input())
while t > 0:
	n = int(input())
	print(n // 2 + 1)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	a = n // 2 + 1
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(n)
	else:
		print(n // 2 + 1)


t = int(input())
i = 0
while i < t:
	n = int(input())
	if n == 2:
		print(n)
	else:
		print(n // 2 + 1)
	i += 1


def cupc(n):
	if n == 2:
		return n
	else:
		return n // 2 + 1
t = int(input())
for i in range(0, t):
	n = int(input())
	print(cupc(n))


n = int(input())
for i in range(n):
	a = int(input())
	rem = a // 2 + 1
	if a <= 2:
		print(a)
	else:
		print(rem)


for i in range(int(input())):
	print(int(input()) // 2 + 1)


for _ in range(int(input())):
	N = int(input())
	print(int(N / 2 + 1))


n = int(input())
for i in range(n):
	p = int(input())
	print(p // 2 + 1)


T = int(input())
for i in range(T):
	N = int(input())
	print(int(N / 2 + 1))


for i in range(int(input())):
	N = int(input())
	if N % 2 == 0 and N == 2:
		print(N)
	elif N % 2 == 0 and N > 2:
		b = 1
		y = abs(N - 4)
		b += y / 2
		print(int(N - b))
	elif N % 2 != 0 and N >= 3:
		a = 1
		x = abs(N - 3)
		a += x / 2
		print(int(N - a))


for T in range(int(input())):
	N = int(input())
	a = N // 2 + 1
	print(a)


t = int(input())
for i in range(t):
	x = int(input())
	print(x // 2 + 1)


t = int(input())
for _ in range(t):
	c = int(input())
	if c == 2:
		print('2')
	else:
		res = c // 2 + 1
		print(res)


def customFunc(n):
	print(n // 2 + 1)
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	customFunc(n)


n = int(input())
for i in range(n):
	x = int(input())
	print(x // 2 + 1)


n = int(input())
for i in range(n):
	y = int(input())
	print(y // 2 + 1)


t = int(input())
for cases in range(t):
	n = int(input())
	k = n // 2
	print(k + 1)
	print()


t = int(input())
for i in range(0, t):
	N = int(input())
	d = N // 2 + 1
	print(d)


Test = int(input())
for Cases in range(Test):
	NumberofCupcakes = int(input())
	Result = NumberofCupcakes // 2 + 1
	print(Result)


for i in range(int(input())):
	n = int(input())
	d = n // 2 + 1
	print(d)


for _ in range(int(input())):
	n = int(input())
	c = 0
	if n < 3:
		c = n
	else:
		c = n // 2 + 1
	print(c)