Description

Haruka gives you three non-negative integers $x, y, p$. You can perform the following two operations any number of times (including zero) in any order:

1. Let $x \gets (x + 1) \mathbin{\vert} p$.
2. Let $x \gets x \mathbin{\vert} (p + 1)$.

Here, $\mathbin{\vert}$ denotes the bitwise OR operation, and $a \gets b$ means assigning the value of $b$ to $a$.

Haruka wants to know whether it is possible to transform $x$ into $y$ through these operations. If possible, she also wants to know the minimum number of operations required.

Please help her solve this problem.

Input Format

The input contains multiple test cases.

The first line contains an integer $T$, indicating the number of test cases. For each test case:

• One line containing three non-negative integers $x, y, p$.

Output Format

For each test case, output one line. If there is a solution, output a non-negative integer representing the minimum number of operations; otherwise, output -1.

8
1 2 4
2 6 5
2 9 1
1 11 2
4 9 2
114514 1919810 2
105 163 33
10000000000 1000000000000000000 262144

-1
1
4
5
-1
902648
13
499999994999741440

Hint

【Sample Explanation】

For the first test case, it can be proven that no sequence of operations exists.

For the second test case, perform operation 2 once: $x$ changes as $2 \to 6$.

For the third test case, perform operation 1 four times: $x$ changes as $2 \to 3 \to 5 \to 7 \to 9$.

【Data Range】

This problem uses bundled testing.

• Special Property A: If a solution exists, there is an optimal solution that uses only operation 1.
• Special Property B: If a solution exists, there is an optimal solution that uses only operation 2.
• Special Property C: $p = 1$.

For all test cases, $1 \le T \le 10^4$, $0 \le x, y, p \le 10^{18}$.

Translated by DeepSeek V3.1