Sum and OR solution codechef
Chef has two integers bitwise OR of their elements is . Chef would like to know the shortest possible length such a sequence can have.and . He is interested in sequences of non-negative integers such that the sum of their elements is and the
Formally, find the smallest positive integersuch that there exists a sequence satisfying the following conditions:
- Each is a non-negative integer
wheredenotes the bitwise OR operation.
If there does not exist any sequence which satisfies the above conditions, output. Otherwise, output the minimum possible length of such a sequence.
- The first line of input contains a single integer , denoting the number of test cases. The description of test cases follows.
- Each test case consists of a single line of input, containing two space-separated integers and — the required bitwise OR and sum, respectively.
For each test case, output a single line containing one integer — the shortest possible length of such a sequence, orif no such sequence exists.
Subtask #1 (100 points): Original constraints
Sample Input 1
3 13 23 6 13 1 25
Sample Output 1
3 -1 25
Test Case: One of the valid arrays of length is . It can be shown that there is no valid array with length .
Test Case: There does not exist any sequence whose sum is and bitwise OR is .
Test Case: The valid array of minimum length contains ones.