A. XO-OR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two integers $$$x$$$ and $$$y$$$, choose an integer $$$v \in [0, x]$$$ such that the size of a set $$$S$$$ of distinct non-negative integers is maximized.

Formally, determine the largest possible size of a set $$$$$$ S = \{ s_1, s_2, \dots, s_m \} $$$$$$ satisfying the following conditions:

  • The bitwise XOR of all elements equals $$$y$$$: $$$$$$ s_1 \oplus s_2 \oplus \cdots \oplus s_m = y. $$$$$$
  • The bitwise OR of all elements equals $$$v$$$: $$$$$$ s_1 \mid s_2 \mid \cdots \mid s_m = v. $$$$$$

Output the maximum possible value of $$$m$$$. If no valid set exists, output $$$-1$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases.

Each test case contains two integers $$$x$$$ and $$$y$$$ $$$(0 \leq x, y \leq 10^{18})$$$.

Output

For each test case, print a single integer  — the maximum possible size of the set $$$S$$$. If no such set can be formed, report $$$-1$$$.

Example
Input
2
2 2
3 0
Output
2
4
Note
  • For the first test case, let $$$(x, y) = (2, 2)$$$ and choose $$$v = 2$$$. The resulting set is defined as: $$$$$$ S = \{0, 2\} $$$$$$
    • XOR of all elements: $$$ 0 \oplus 2 = 2 $$$
    • OR of all elements: $$$ 0 \mid 2 = 2 $$$

  • For the second test case, let $$$(x, y) = (3, 0)$$$ and choose $$$v = 3$$$. The resulting set is defined as: $$$$$$ S = \{0, 1, 2, 3\} $$$$$$
    • XOR of all elements: $$$ 0 \oplus 1 \oplus 2 \oplus 3 = 0 $$$
    • OR of all elements: $$$ 0 \mid 1 \mid 2 \mid 3 = 3 $$$