Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

As usual, Tom and Jerry are fighting. Tom has strength $TS$ and Jerry has strength $JS$. You are given $TS$ and your task is to find the number of possible values of $JS$ such that Jerry wins the following game.

The game consists of one or more turns. In each turn:
If both $TS$ and $JS$ are even, their values get divided by $2$ and the game proceeds with the next turn.
If both $TS$ and $JS$ are odd, a tie is declared and the game ends.
If $TS$ is even and $JS$ is odd, Tom wins the game.
If $TS$ is odd and $JS$ is even, Jerry wins the game.

Find the number of possible initial values of $JS$ such that $1 ≤ JS ≤ TS$, there is no tie and Jerry wins the game.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $TS$.

------  Output ------
For each test case, print a single line containing one integer ― the number of values of $JS$ such that Jerry wins the game.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ TS ≤ 10^{18}$

------  Subtasks ------
Subtask #1 (20 points): $T, TS ≤ 100$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2

1

11
----- Sample Output 1 ------ 
0

5
----- explanation 1 ------ 
Example case 1: We must have $JS = TS = 1$, but in this case, the game ends and a tie is declared in the first turn.

Example case 2: If $JS \in \{2, 4, 6, 8, 10\}$, then $JS$ is even and $TS$ is odd, so Jerry wins the game in the first turn. Any odd value of $JS$ leads to a tie instead.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
t = int(input())
for ni in range(t):
	ts = int(input())
	if ts % 2 == 1:
		print(ts // 2)
	else:
		while ts % 2 == 0:
			ts = ts // 2
		print(ts // 2)


for tc in range(int(input())):
	ts = int(input())
	while ts % 2 == 0:
		ts = ts // 2
	j = ts // 2
	print(j)


for _ in range(int(input())):
	t = int(input())
	(tc, t2) = (t, 1)
	while not tc % 2:
		t2 += 1
		tc //= 2
	print(t // 2 ** t2)


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


def sol(n):
	if n < 3:
		print(0)
	elif n % 2 == 0:
		sol(n // 2)
	else:
		print(n // 2)
for _ in range(int(input())):
	n = int(input())
	sol(n)


for _ in range(int(input())):
	n = int(input())
	while n % 2 == 0:
		n //= 2
	print(n // 2)


import math
for _ in range(int(input())):
	ts = int(input())
	n = 0
	if ts % 2 == 0:
		while ts % 2 == 0:
			n += 1
			ts = ts // 2
		print(int(ts) // 2)
	else:
		print(int(ts) // 2)


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


for i in range(int(input())):
	ts = int(input())
	ts1 = ts
	cnt = 0
	while ts1 % 2 == 0:
		ts1 = ts1 // 2
		cnt += 1
	print(ts // 2 ** (cnt + 1))


for _ in range(int(input())):
	ts = int(input())
	tom = ts
	power = 0
	while tom % 2 == 0:
		tom = tom // 2
		power += 1
	print(ts // 2 ** (power + 1))


tc = int(input())
for _ in range(tc):
	tom = int(input())
	tom1 = tom
	power = 0
	while tom1 % 2 == 0:
		tom1 = tom1 // 2
		power += 1
	print(tom // 2 ** (power + 1))


n = int(input())
for i in range(n):
	s = int(input())
	while s % 2 == 0:
		s = s // 2
	print(s // 2)


for i in range(int(input())):
	ts = int(input())
	while ts % 2 == 0:
		ts //= 2
	print(ts // 2)


for _ in range(int(input())):
	ts = int(input())
	while ts % 2 == 0:
		ts //= 2
	print(ts // 2)


for _ in range(int(input())):
	l = int(input())
	y = l
	k = 0
	while l % 2 == 0:
		k += 1
		l = l // 2
	x = 2 ** (k + 1)
	print(y // x)


t = input()
for c in range(0, int(t)):
	l = int(input())
	y = l
	k = 0
	while l % 2 == 0:
		k += 1
		l = l // 2
	x = 2 ** (k + 1)
	print(y // x)


t = int(input())
for i in range(t):
	tom = int(input())
	ans = 0
	if tom % 2 != 0:
		ans = tom // 2
	else:
		div = 1
		otom = tom
		while tom % 2 == 0:
			tom = tom // 2
			div = div * 2
		div = div * 2
		ans = otom // div
	print(ans)


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	log_val = math.log(num, 2)
	if num == 1 and int(log_val) == log_val:
		print(0)
	else:
		while not num & 1:
			num //= 2
		print(num // 2)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(n // 2)
	else:
		while n:
			n = n // 2
			if n % 2 == 1:
				print(n // 2)
				break
		else:
			print(0)


for _ in range(int(input())):
	ts = int(input())
	x = ts
	y = 0
	while ts % 2 == 0:
		y += 1
		ts = ts // 2
	a = 2 ** (y + 1)
	print(x // a)


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


for t in range(int(input())):
	ts = int(input())
	num_of_twos = 0
	tsc = ts
	while tsc % 2 == 0:
		tsc = tsc // 2
		num_of_twos += 1
	print(ts // pow(2, num_of_twos + 1))


for t in range(int(input())):
	ts = int(input())
	num_of_twos = 0
	tsc = ts
	while tsc % 2 == 0:
		tsc = tsc // 2
		num_of_twos += 1
	m = pow(2, num_of_twos + 1)
	ans = ts // m if m < ts else 0
	print(ans)


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


for i in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print((n - 1) // 2)
	else:
		count = 0
		res = n
		while n % 2 == 0:
			n //= 2
			count += 1
		ans = res // 2 ** (count + 1)
		print(ans)


for _ in range(int(input())):
	n = int(input())
	i = 1
	for _ in range(n):
		i *= 2
		if n % i != 0:
			print(n // i)
			break


t = int(input())
for i in range(t):
	n = int(input())
	while n > 0:
		if n % 2 == 0:
			n //= 2
		else:
			print(n // 2)
			break


t = int(input())
for i in range(t):
	ts = int(input())
	while ts > 0:
		if ts % 2 != 0:
			ts = ts - 1
			print(ts // 2)
			break
		else:
			ts = ts // 2


ujju = int(input())
for sai in range(ujju):
	us = int(input())
	if us % 2 != 0:
		print(us // 2)
	else:
		pr = 1
		uss = us
		while us % 2 == 0:
			us //= 2
			pr *= 2
		pr *= 2
		print(uss // pr)


T = int(input())
for t in range(0, T):
	JS = 0
	TS = int(input())
	while TS % 2 == 0:
		TS = TS // 2
	if TS % 2 != 0:
		JS = TS // 2
	print(int(JS))


try:
	t = int(input())
	for i in range(t):
		count = 0
		n = int(input())
		while n % 2 == 0:
			n = n // 2
		print(n // 2)
except:
	pass


for _ in range(int(input())):
	ts = int(input())
	if ts % 2 == 0:
		while ts % 2 == 0:
			ts = ts // 2
		print(ts // 2)
	else:
		print(ts // 2)


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


def solve():
	TS = int(input())
	while TS & 1 ^ 1:
		TS //= 2
	print(TS // 2)
t = int(input())
while t > 0:
	solve()
	t -= 1


def strength(ts):
	if ts == 1:
		return 0
	k = 0
	while ts % 2 == 0:
		k += 1
		ts = ts // 2
	return ts // 2
t = int(input())
for _ in range(t):
	ts = int(input())
	print(strength(ts))


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


for t in range(int(input())):
	ts = int(input())
	while ts % 2 == 0:
		ts = ts // 2
	print(ts // 2)


try:
	for _ in range(int(input())):
		n = int(input())
		while n % 2 == 0:
			n = n // 2
		print(n // 2)
except:
	pass


for i in range(int(input())):
	ts = int(input())
	if ts % 2 != 0:
		print(ts // 2)
	else:
		div = 1
		n_ts = ts
		while ts % 2 == 0:
			ts = ts // 2
			div = div * 2
		div = div * 2
		print(n_ts // div)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	while n % 2 == 0:
		n //= 2
	print(n // 2)


for t in range(int(input())):
	ts = int(input())
	if ts % 2 == 1:
		js = ts - 1
		ans = js // 2
		print(ans)
	else:
		while ts % 2 == 0:
			ts = ts // 2
		js = ts - 1
		print(js // 2)


for t in range(int(input())):
	ts = int(input())
	while ts % 2 == 0:
		ts = ts // 2
	js = ts - 1
	print(js // 2)


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


_t = int(input())
while _t > 0:
	ts = int(input())
	while ts % 2 != 1:
		ts //= 2
	print(ts // 2)
	_t -= 1


def solve(ts):
	if ts % 2 == 0:
		while ts % 2 == 0 and ts != 0:
			ts //= 2
		if ts == 0:
			return 0
		else:
			return ts // 2
	else:
		return ts // 2
t = int(input())
for _ in range(t):
	ts = int(input())
	print(solve(ts))


class Solution:

	def solve(self, ts):
		if ts % 2 == 0:
			while ts % 2 == 0 and ts != 0:
				ts //= 2
			if ts == 0:
				return 0
			else:
				return ts // 2
		else:
			return ts // 2
t = int(input())
for _ in range(t):
	ts = int(input())
	obj = Solution()
	print(obj.solve(ts))


t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	for i in range(n):
		if n % 2 == 0:
			n //= 2
		else:
			break
	print(n // 2)


t = int(input())
for i in range(t):
	s = int(input())
	if s % 2 == 0:
		while s % 2 == 0:
			s = s // 2
		print(s // 2)
	else:
		print(s // 2)


def cnt(n):
	temp = 1
	while n % 2 == 0:
		temp = temp * 2
		n = n // 2
	return temp * 2
for _ in range(int(input())):
	ts = int(input())
	print(ts // cnt(ts))


def even_calc(x, i):
	while x % 2 == 0:
		x = x // 2
	if x < 3:
		return 0
	return (x - 1) // 2

def calculate(x):
	value = x // 2
	if x == 0:
		print(0)
	elif x % 2 == 0:
		print(even_calc(x, 1))
	else:
		print(x // 2)
t = int(input())
for i in range(t):
	x = int(input())
	calculate(x)


for i in range(int(input())):
	a = int(input())
	while a % 2 == 0:
		a = a // 2
	print(a // 2)


for _ in range(int(input())):
	ts = int(input())
	two_pow = 1
	t = ts
	while t % 2 == 0:
		t //= 2
		two_pow += 1
	div = 2 ** two_pow
	odds = lambda x: (x - 1) // 2 + 1
	js = 0
	while ts // div > 0:
		js += odds(ts // div)
		div *= 2
	print(js)


for _ in range(int(input())):
	ts = int(input())
	if ts % 2 != 0:
		print(ts // 2)
	else:
		i = 2 ** len(bin(ts)[2:])
		while ts % 2 == 0 and ts != 1 and (i > 1):
			ts = ts // 2
			i = i // 2
		print(ts // 2)


x = int(input())
while x:
	ts = int(input())
	if ts % 2 != 0:
		js = (ts - 1) // 2
		print(js)
	else:
		while ts % 2 == 0:
			ts = ts // 2
		js = (ts - 1) // 2
		print(js)
	x = x - 1


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