You are given an integer K.

Consider an integer sequence A = [A_{1}, A_{2}, \ldots, A_{N}].

Define another sequence S of length N, such that S_{i} = A_{1} + A_{2} + \ldots + A_{i} for each 1 ≤ i ≤ N.

A is said to be *interesting* if A_{i} + S_{i} = K for every 1 ≤ i ≤ N.

Find the maximum length of an interesting sequence. If there are no interesting sequences, print 0.

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

- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input, which contains a single integer K.

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

- For each test case, print a new line containing one integer — the maximum length of an *interesting* sequence for a given value of K.

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

$1 ≤ T ≤ 5000$
$1 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
2
8
4
----- Sample Output 1 ------ 
3
2
----- explanation 1 ------ 
Test Case $1$: Consider the sequence $A = [4, 2, 1]$. $S = [4, 4 + 2, 4 + 2 + 1] = [4, 6, 7]$. 
The sum of the corresponding elements of $A$ and $S$ are $4 + 4 = 8$, $2 + 6 = 8$ and $1 + 7 = 8$. Thus $A$ is an interesting sequence of size $3$.  

Test Case $2$: Consider the sequence $A = [2, 1]$. $S = [2, 2 + 1] = [2, 3]$. 
The sum of the corresponding elements of $A$ and $S$ are $2 + 2 = 4$ and $1 + 3 = 4$. Thus $A$ is an interesting sequence of size $2$.

It's guaranteed that, in both examples above, there doesn't exist a longer sequence satisfying the problem constraints.

Difficulty: EASY

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	i = 2
	c = 0
	while n % i == 0:
		i *= 2
		c += 1
	print(c)


t = int(input())
for xvdf in range(t):
	k = int(input())
	if k % 2:
		print(0)
	else:
		c = 0
		while k > 1:
			k //= 2
			c += 1
			if k % 2 == 1:
				break
		print(c)


try:
	for i in range(int(input())):
		index = -1
		count = 1
		k = int(input())
		if k % 2 == 0:
			k = k // 2
			while k % 2 == 0:
				count += 1
				index = 1
				k = k // 2
			print(count)
		else:
			print(0)
except:
	pass


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


for _ in range(int(input())):
	K = int(input())
	K = int(format(K, 'b'), base=2)
	count = 0
	while K & 1 == 0:
		K = K >> 1
		count += 1
	print(count)


for _ in range(int(input())):
	k = int(input())
	if k & 1:
		print(0)
	else:
		c = 0
		while k > 0:
			if k % 2 == 0:
				c += 1
				k = k / 2
			else:
				break
		print(c)


t = int(input())
for i in range(t):
	k = int(input())
	x = 1
	count = 0
	while k % 2 ** x == 0:
		count = count + 1
		x = x + 1
	print(count)


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


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


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


T = int(input())
for tc in range(T):
	k = int(input())
	ans = 0
	if k % 2 == 0:
		while k % 2 == 0:
			k = k // 2
			ans += 1
		print(ans)
	else:
		print(0)


import math
for _ in range(int(input())):
	k = int(input())
	temp = bin(k)[2:]
	print(len(temp) - len(temp.rstrip('0')))


p = []
for x in range(50):
	p.append(pow(2, x))
for i in range(int(input())):
	c = 0
	n = int(input())
	if p.count(n) > 0:
		print(p.index(n))
	else:
		while n % 2 == 0:
			c = c + 1
			n = n / 2
			if n % 2 != 0:
				break
		print(c)


def even(x, sum):
	if x % 2 == 0:
		x //= 2
		sum += 1
		return even(x, sum)
	else:
		return sum
t = int(input(''))
if 1 <= t <= 5000:
	for _ in range(t):
		k = int(input(''))
		if 1 <= k <= 10 ** 9:
			if k % 2 == 0:
				sum = 0
				print(even(k, sum))
			else:
				print(0)


for _ in range(int(input())):
	k = int(input())
	a = k
	count = 0
	flag = 0
	if a % 2 != 0:
		print('0')
	else:
		while a % 2 == 0:
			count += 1
			a = a // 2
		print(count)


for _ in range(int(input())):
	a = int(input())
	b = a
	c = 0
	if a % 2 != 0:
		print(0)
		continue
	else:
		while b % 2 == 0:
			b //= 2
			c += 1
	print(c)


for t in range(int(input())):
	n = int(input())
	c = 0
	while n > 0 and n % 2 == 0:
		n /= 2
		c += 1
	print(c)


t = input()
for c in range(0, int(t)):
	k = int(input())
	count = 0
	if k % 2 == 0:
		while k % 2 == 0:
			count += 1
			k = k // 2
		print(count)
	else:
		print('0')


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


def power(n):
	for i in range(0, n // 2):
		n = n / 2
		if n == 1:
			return i + 1
		elif n % 2 != 0:
			return i + 1
T = int(input())
for i in range(0, T):
	k = int(input())
	if k % 2 != 0:
		print(0)
	else:
		print(power(k))


def Seq(K):
	count = 0
	while K % 2 == 0:
		K = int(K / 2)
		count += 1
	print(count)
numbertest = int(input())
for i in range(numbertest):
	K = int(input())
	Seq(K)


from math import log
for _ in range(int(input())):
	k = int(input())
	ans = 0
	while k % 2 == 0:
		ans += 1
		k = int(k / 2)
	print(ans)


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


tests = int(input())
for i in range(tests):
	num = int(input())
	arr = []
	required = num // 2
	while required > 0 and sum(arr) + 2 * required == num:
		arr.append(required)
		required = (num - sum(arr)) // 2
	print(len(arr))


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


for _ in range(int(input())):
	n = int(input())
	l = 0
	i = n // 2
	s = 0
	while i > 0:
		if s + i * 2 != n:
			break
		l += 1
		s += i
		i = i // 2
	print(l)


for _ in range(int(input())):
	k = int(input())
	l = []
	re = -2
	le = 0
	if k % 2 != 0:
		print(0)
	else:
		while re != 0:
			if re % 2 != 0:
				le = len(l)
				break
			elif len(l) != 0:
				re = (k - sum(l)) // 2
				l.append(re)
			else:
				re = k // 2
				l.append(re)
		if le != 0:
			print(le)
		else:
			print(len(l) - 1)


import math
t = int(input())
for l in range(t):
	n = int(input())
	ans = 0
	while n % 2 == 0:
		n //= 2
		ans += 1
	print(ans)


import math

def p2(x):
	return x and (not x & x - 1)

def sqrt(x):
	c = 0
	while x % 2 == 0:
		x //= 2
		c += 1
	return c
for _ in range(int(input())):
	k = int(input())
	x = sqrt(k)
	print(x)


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


case = int(input())
for _ in range(case):
	k = int(input())
	x = 0
	while True:
		if k % 2 == 0:
			x = x + 1
			k = k // 2
		else:
			print(x)
			break


from math import log
for i in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		tot = 0
		while n % 2 == 0:
			n //= 2
			tot += 1
		print(tot)
	else:
		print(0)


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


T = int(input())

def index_s(i, a):
	return sum(a[:i])
for i in range(T):
	k = int(input())
	if not k % 2 == 0:
		print(0)
	else:
		a_1 = int(k / 2)
		a = [a_1]
		s = [a_1]
		i = 2
		while (k - s[-1]) % 2 == 0:
			a_i = int((k - s[-1]) / 2)
			a.append(a_i)
			s_i = index_s(i, a)
			s.append(s_i)
			i += 1
		print(len(a))


def recur(k):
	if k % 2 == 0:
		l.append(int(k / 2))
		recur(int(k / 2))
	if k == 1:
		return len(l)
	else:
		return len(l)
for _ in range(int(input())):
	k = int(input())
	l = []
	print(recur(k))


for tc in range(int(input())):
	k = int(input())
	if k % 2 != 0:
		print(0)
	else:
		print(bin(k)[::-1].index('1'))


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


T = int(input())
for i in range(0, T):
	a = int(input())
	s = 0
	while a % 2 == 0:
		a = a / 2
		s += 1
	print(s)


def solve(n):
	res = 0
	while n % 2 == 0:
		res += 1
		n //= 2
	return res
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


import math

def power_of_2(x):
	return x and (not x & x - 1)
for _ in range(int(input())):
	k = int(input())
	ans = 0
	while k % 2 == 0:
		ans += 1
		k = k // 2
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	x = math.log(n, 2)
	count = 0
	for i in range(math.ceil(x)):
		if n % 2 == 0:
			count += 1
			n = n / 2
	print(count)


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


t = int(input())
for j in range(t):
	a = int(input())
	l = []
	b = a
	while a > 0:
		if a % 2 == 0:
			a = a // 2
			l.append(a)
			if a == 1:
				print(len(l))
				a = 0
		else:
			print(len(l))
			a = 0


t = int(input())
import math
for i in range(t):
	k = int(input())
	if k % 2:
		print(0)
	else:
		a = math.log(k, 10)
		b = math.log(2, 10)
		if a % b == 0:
			print(int(a // b))
		else:
			ans = 0
			while k % 2 == 0:
				k = k / 2
				ans = ans + 1
			print(ans)


ans = []
for i in range(int(input())):
	x = int(input())
	res = 0
	while x % 2 != 1:
		res += 1
		x = x / 2
	ans.append(res)
print(*ans, sep='\n')


import math
T = int(input())
for t in range(1, T + 1):
	K = int(input())
	x = math.log2(K)
	if x.is_integer():
		print(int(x))
		continue
	else:
		num = 0
		i = 1
		while True:
			if (K / 2 ** i).is_integer():
				num = i
				i += 1
			else:
				break
		print(num)
		continue
	print(0)


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


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


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


import math
t = int(input())
for _ in range(t):
	k = int(input())
	if k % 2 == 1:
		print(0)
	else:
		s = set()
		while k % 2 == 0:
			s.add(k // 2)
			k = k // 2
		print(len(s))


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		s = set()
		while n % 2 == 0:
			s.add(n // 2)
			n = n // 2
		print(len(s))


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 != 0:
		print(0)
	else:
		ans = int(math.log(n, 2))
		if n & n - 1 == 0:
			print(ans)
		else:
			c = 0
			while True:
				if n % 2 != 0:
					break
				else:
					c += 1
					n = n // 2
			print(c)


for _ in range(int(input())):
	k = int(input())
	if k % 2 == 1:
		print(0)
	else:
		a = set()
		while k % 2 == 0:
			a.add(k // 2)
			k = k // 2
		print(len(a))


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


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


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


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