Cherry isn't feeling well right now as she found a problem that she couldn't solve. So she started to listen to On the Sea and you, to make her happy, have to solve the problem for her.
For any non-negative integer , let be the median of the submasks of .
You are given two integers and . You have to find the median of the sequence .
An integer is a submask of if can be obtained by replacing some (possibly none or all) -s in the binary representation of by -s.
The median of a sequence is the value of an element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used. For example, the median of is since after sorting the sequence, it will look like
$[2,4,5,7]$ and the left of two middle elements is equal to . The median of equals since after sorting, the value will be in the middle of the sequence.
The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
The first and only line of each test case contains two space-separated integers and .
For each test case, print a single line containing the median of the of the sequence .
3 1 5 7 10 696969 69696969
0 1 8073418
In the second test case,
The sorted list of the submasks of is , so .
So we have to find the median of the sequence , and the list of these values is , and finally, the median of this list is .
Login to submit