Question
Gem Quest
In the magical land of Viondra, mystic Zara searches for a distinct number within the bounds L and R.
The number must contain precisely K shining jewels, represented by the set bits in its binary form.
Assist Zara in locating this number or determining if it doesn’t exist in the range.
The number must contain precisely K shining jewels, represented by the set bits in its binary form.
Assist Zara in locating this number or determining if it doesn’t exist in the range.
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.
The first line of each test case consists of three integers L, R, and K.
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.