Sum and OR solution codechef – Chef has two integers XX and SS. He is interested in sequences of non-negative integers such that the sum of their elements is SS and the bitwise OR of their elements is XX. Chef would like to know the shortest possible length such a sequence can have.

Sum and OR solution codechef

Chef has two integers XX and SS. He is interested in sequences of non-negative integers such that the sum of their elements is SS and the bitwise OR of their elements is XX. Chef would like to know the shortest possible length such a sequence can have.

Formally, find the smallest positive integer NN such that there exists a sequence A=[A1,A2,,AN]A=[A1,A2,…,AN] satisfying the following conditions:

  • Each AiAi is a non-negative integer
  • A1+A2++AN=SA1+A2+…+AN=S
  • A1A2AN=XA1∨A2∨…∨AN=X

where  denotes the bitwise OR operation.

If there does not exist any sequence which satisfies the above conditions, output 1−1. Otherwise, output the minimum possible length of such a sequence.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of a single line of input, containing two space-separated integers XX and SS — the required bitwise OR and sum, respectively.

Output Format

For each test case, output a single line containing one integer — the shortest possible length of such a sequence, or 1−1 if no such sequence exists.

Constraints

  • 1T10001≤T≤1000
  • 1XS1091≤X≤S≤109

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

3
13 23
6 13
1 25

Sample Output 1 

3
-1
25

Explanation

Test Case 11: One of the valid arrays of length 33 is [9,9,5][9,9,5]. It can be shown that there is no valid array with length <3<3.

Test Case 22: There does not exist any sequence whose sum is 1313 and bitwise OR is 66.

Test Case 33: The valid array of minimum length contains 2525 ones.

Leave a Comment

Your email address will not be published.