• # For Solution

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

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.