Question
Find Number with Set Bits
In a magical kingdom, a wizard named Arjun has three numbers: l, r, and k. The numbers l and r define a range, and Arjun is searching for a special number within this range (inclusive) that has exactly k set bits in its binary form.
Your task is to help Arjun find a number between l and r that meets this condition. If such a number exists, guide Arjun to it!
Your task is to help Arjun find a number between l and r that meets this condition. If such a number exists, guide Arjun to it!
Input
The first line contains one integer T denoting the number of test cases.
The first line of each test case consists of three integers l, r, and k.
.Constraints:
1 ≤ l,r ≤ 1018
1 ≤ k ≤ 64
1 ≤ T ≤ 105
The first line of each test case consists of three integers l, r, and k.
.Constraints:
1 ≤ l,r ≤ 1018
1 ≤ k ≤ 64
1 ≤ T ≤ 105
Output
For every test case, print one integer denoting the answer to the problem.
If there are multiple such numbers present in the range, print the minimum among such numbers.
If no number satisfies the above condition, print -1.
If there are multiple such numbers present in the range, print the minimum among such numbers.
If no number satisfies the above condition, print -1.
Example
Sample Input
4
1 10 1
1 10 2
1 10 3
1 10 4
Sample Output
1
3
7
-1
Explanation:
Test case 1: The minimum number in the range 1 - 10 with 1 set bit is 1 (0001).
Test case 2: The minimum number in the range 1 - 10 with 2 set bits is 3 (0011).
Test case 3: The minimum number in the range 1 - 10 with 3 set bits is 7 (0111).
Test case 4: No number is present in the range 1 - 10 with 4 set bit counts.
4
1 10 1
1 10 2
1 10 3
1 10 4
Sample Output
1
3
7
-1
Explanation:
Test case 1: The minimum number in the range 1 - 10 with 1 set bit is 1 (0001).
Test case 2: The minimum number in the range 1 - 10 with 2 set bits is 3 (0011).
Test case 3: The minimum number in the range 1 - 10 with 3 set bits is 7 (0111).
Test case 4: No number is present in the range 1 - 10 with 4 set bit counts.