Akash has his maths test tomorrow. He secretly found out one of the questions from the test.
As the test is online, he wants to write a code that solves the question. However, he is not good at coding and thus, wants Chef to help him with that.

Chef is given a function F(X) such that the condition:
F(X) = F(2\cdot X)  
holds true for all X, where X is a positive integer.

For a given positive integer N, find the maximum number of distinct elements in the array [F(1), F(2), F(3), \ldots, F(N)].

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

- First line will contain T - the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, one integer N.

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

For each test case, output in a single line, the maximum number of distinct elements in the array [F(1), F(2), F(3), \ldots, F(N)].

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{9}$

------ subtasks ------ 

Subtask 1 (30 points): $1 ≤ N ≤ 1000$
Subtask 2 (70 points): Original Constraints.

----- Sample Input 1 ------ 
2
2
5
----- Sample Output 1 ------ 
1
3
----- explanation 1 ------ 
Test case $1$: Let $X = 1$. Thus, $2 = 2\cdot 1 = 2\cdot X$. Therefore, $F(1) = F(2)$. So, in the array $[F(1), F(2)]$, there is only $1$ distinct element.

Test case $2$: Here, we can take $X = 1$. Thus $F(1) = F(2)$. Similarly, if we take $X = 2$, $F(2) = F(4)$. This means that $F(1) = F(2) = F(4)$.  
However, it can be possible that the values $F(1), F(3),$ and $F(5)$ are distinct. Hence, the maximum number of distinct elements in the array $[F(1), F(2), F(3), F(4), F(5)]$ is $3$.

Difficulty: EASY
Tags: Mathematics

Starter code:

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


s = int(input())
for i in range(s):
	a = int(input())
	print(a - a // 2)


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


import math
for _ in range(int(input())):
	n = int(input())
	print(math.ceil(n / 2))


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


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


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


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	if n % 2 != 0:
		ans = n // 2 + 1
		print(ans)
	else:
		ans = n // 2
		print(ans)


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	print(-(-wife // 2))


import math
t = int(input())
for i in range(t):
	n = int(input())
	print(math.ceil(n / 2))


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


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


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


import math as m
for i in range(int(input())):
	n = int(input())
	print(m.ceil(n / 2))


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


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


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


import math

def solve():
	return n - n // 2
for _ in range(int(input())):
	n = int(input())
	print(solve())


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


for _ in range(int(input())):
	N = int(input())
	print(N // 2 + 1) if N % 2 != 0 else print(N // 2)


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


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


t = int(input())
while t > 0:
	a = 1
	c = 0
	x = int(input())
	if x % 2 != 0:
		a = (x - 1) // 2
		print(x - a)
	else:
		a = x // 2
		print(a)
	t -= 1


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


import math
T = int(input())
x = range(T)
for i in x:
	n = int(input())
	print(math.ceil(n / 2))


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


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


for i in range(int(input())):
	f = int(input())
	if f % 2 == 0:
		print(f // 2)
	else:
		ans = f // 2 + 1
		print(ans)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	sys.stdout.write(str(n // 2) + '\n' if n % 2 == 0 else str(n // 2 + 1) + '\n')