Chef is playing badminton today. The service rules of this singles game of badminton are as follows:
1. The player who starts the game serves from the right side of their court.
2. Whenever a player wins a point, they serve next.
3. If the server has won an even number of points during a game, then they will serve from the right side of the service court for the subsequent point.

Chef will be the player who begins the game.

Given the number of points P obtained by Chef at the end of the game, please determine how many times Chef served from the right side of the court.

Please see the sample cases below for explained examples.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line containing one integer P, the points obtained by Chef.

------ Output Format ------ 

For each test case, output in a single line the number of times Chef served from the right side of the court.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$0 ≤ P ≤ 10^{9}$

----- Sample Input 1 ------ 
4
2
9
53
746
----- Sample Output 1 ------ 
2
5
27
374
----- explanation 1 ------ 
Test case $1$: Chef obtained $2$ points at the end of the game. This means he served two times from the right side of the court, once when his score was $0$ and once again when his score was $2$.

Test case $2$: Chef obtained $9$ points at the end of the game. This means he served $5$ times from the right side of the court. The points when he had to serve from right were: $0,2,4,6,8$.

Difficulty: EASY
Tags: Constructive algorithms

Implementation

Ad-hoc

Starter code:

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


for item in range(int(input())):
	point = int(input())
	print(point // 2 + 1)


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


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


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


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


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


T = int(input())
for _ in range(T):
	p = int(input())
	next = 1
	if p % 2 == 0:
		print(p // 2 + 1)
		next = 1
	else:
		print(p // 2 + next)
		next = 0


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


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


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


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


T = int(input())
while T > 0:
	p = int(input())
	ans = p // 2 + 1
	print(ans)
	T -= 1


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


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


import math
T = int(input())
for i in range(T):
	P = int(input())
	if P % 2 == 0:
		print(int(P / 2 + 1))
	else:
		print(math.ceil(P / 2))


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


def code():
	cases = int(input())
	for _ in range(cases):
		P = int(input())
		print(int(P // 2 + 1))
code()


def code():
	cases = int(input())
	for _ in range(cases):
		P = int(input())
		if P % 2 == 0:
			print(int(P / 2 + 1))
		else:
			print(int(P // 2 + 1))
code()


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


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


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


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


import numpy as math
for _ in range(int(input())):
	x = int(input())
	if x % 2 == 0:
		print(x // 2 + 1)
	else:
		print(int(math.ceil(x / 2)))


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


t = int(input())
for i in range(t):
	p = int(input())
	if p == 2:
		print(2)
	elif p % 2 == 0:
		print(p // 2 + 1)
	elif p % 2 != 0:
		print(p // 2 + 1)


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


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


try:
	t = int(input())
	for r in range(t):
		p = int(input())
		a = p // 2
		print(a + 1)
except:
	pass


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


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


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


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


goals = int(input())
for distractions in range(goals):
	life = int(input())
	print(life // 2 + 1)


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


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