lucky-string-jackpot-1

Kuldeep's girlfriend Christie recently got her PhD in Maths. So to celebrate, they both decided to play games with mathematical sequences for their date nights.

The game they are playing today is "Jackpot Palindrome", the objective of the game is to find out length of the largest palindrome which only contains the digit "4" from a given string.

The reference string for today is the lucky string. Lucky string is the concatenation of all lucky numbers in ascending order.
 Lucky numbers are those numbers which contain only "4" and/or "5". For example 4, 5, 44, 54,55,444 are lucky numbers while 457, 987 ,154 are not.
So the fist few digits of the lucky string are "4544455455444445454455..." .

Since the lucky string is infinite, Christie gives Kuldeep an integer N and Kuldeep only needs to consider the lucky string upto length N.

Everytime Kuldeep answers correctly, he gets a kiss from Christie, obviously he'd want to maximize the number of kisses he gets, so your task is to help Kuldeep answer correctly everytime.

Input:
First line contains no of test cases T.
Next T lines contains a single integer N.

Output:
A single integer which is length of the largest palindrome substring containing only digit "4" in lucky string of length N.

Constraints:
1 ≤ T ≤ 100000
1 ≤ N ≤ 10^15

SAMPLE INPUT
4
1
2
3
4

SAMPLE OUTPUT
1
1
1
2

Source: hackerearth | Difficulty: MEDIUM


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T = int(input())
 
t = 0
 
while(t<T):
	t = t+1
	N = int(input())
	n = N
	length = 1
	while( (n - 2*length + 1) >= 0):
		n = n - (2**length)*length
		length = length + 1
	
	length = length - 1
	
	m = 2*length - 1
	
	if(m > n):
		print('%d' %m)
	else:
		print('%d' %n)
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T = int(input())

t = 0

while(t<T):
	t = t+1
	N = int(input())
	n = N
	length = 1
	while( (n - 2*length + 1) >= 0):
		n = n - (2**length)*length
		length = length + 1
	
	length = length - 1
	
	m = 2*length - 1
	
	if(m > n):
		print('%d' %m)
	else:
		print('%d' %n)
	
	


t=eval(input())
for i in range(t):
	N=eval(input())
	n=N
	l=1
	while ((n-2*l+1)>=0):
		n=n-(2**l)*l
		l+=1
	l=l-1
	m=2*l-1
	if m>n:
		print(m)
	else:
		print(n)


t=eval(input())
for i in range(t):
	N=eval(input())
	n=N
	l=1
	while ((n-2*l+1)>=0):
		n=n-(2**l)*l
		l+=1
	l=l-1
	m=2*l-1
	if m>n:
		print(m)
	else:
		print(n)


t=eval(input())
for i in range(t):
	N=eval(input())
	n=N
	l=1
	while ((n-2*l+1)>=0):
		n=n-(2**l)*l
		l+=1
	l=l-1
	m=2*l-1
	if m>n:
		print(m)
	else:
		print(n)