karan-and-trees

Karan performed poorly in the Capillary Java Hiring Challenge because he did not know the concept of trees. After the contest, he asks you to help him out in the questions.

Given two nodes of a binary tree, you need to tell the lowest common ancestor.

The root node is 1 and the general form of left node is 2n and of right node is 2n+1, where n is the parent.

Input:

The first line contains the number of test cases T. Each test case contains two space separated integers, the nodes.

Output:

The Lowest Common Ancestor, one per line.

Constraints:

1 ≤ T ≤ 1000

1 ≤ a,b ≤ 10^18
This is the last question in the contest. Hope you had a great time!!! Keep practising :)
Thanks to Sri Patel for pointing out the language problem in the statement. Any inconvenience is regretted.

SAMPLE INPUT
1
2 3

SAMPLE OUTPUT
1

Source: hackerearth | Difficulty: EASY
Tags: Tree algorithms

Fundamentals


Solutions:
test = int(input())
for i in range(test):
	a , b = [int(x) for x in input().split()]
	p1 = a
	p2 = b
	while p1 != p2:
		if p1 > p2:
			if p1 % 2 == 0:
				p1 /= 2
			else:
				p1 = ( p1  - 1) / 2
		elif p2 > p1:
			if p2 % 2 == 0:
				p2 /= 2
			else:
				p2 = ( p2  - 1) / 2
	print(p1)


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
for _ in range(int(input())):
	a,b = list(map(int, input().split()))
	list_a = []
	i = a
	while i > 0:
		list_a.append(i)
		i /= 2
	list_b = []
	i = b
	while i > 0:
		list_b.append(i)
		i /= 2
	list_a = list_a[::-1]
	list_b = list_b[::-1]
	i = 0
	while i < len(list_a) and i < len(list_b):
		if(list_a[i] != list_b[i]):
			break
		i += 1
	print(list_b[i-1])


t = int(input())
while t>0:
	t -= 1
	a,b = list(map(int,input().split()))
	while True:
		if a==b:
			print(a)
			break
		elif a>b:
			a /= 2
		elif b>a:
			b /= 2
		


import sys

def main(file):
	''' Main '''
	T = int(file.readline().strip())
	
	lines = file.readlines()

	for line in lines:
		a, b = list(map(int, line.strip().split(" ")))		
		
		while a > 1 and b > 1 and a != b :
			if b > a:
				b /= 2
			else:
				a /= 2
		
		print(min(a, b))
			
		
if __name__ == "__main__":
	main(sys.stdin)


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

t = int(input())
for i in range(t):
	a,b = list(map(int,input().split()))
	while(a != b):
		if a > b:
			if a % 2==0:
				a = a/2
			else:
				a = (a -1)/2
		elif b > a:
			if b % 2==0:
				b=b/2
			else:
				b = (b-1)/2
	print(a)


def parent(a,b):
	p1 = a
	p2 = b
	while p1!=p2:
		if p1>p2:
			p1 /= 2
		else:
			p2 /= 2
		#print p1, p2
	return p1
for i in range(eval(input())):
	a , b = list(map(int,input().split()))
	print(parent(a, b))