JJ has three integers A, B, and N. He can apply the following operation on A:
Select an integer X such that 1 ≤ X < N and set A :$= A \oplus X. (Here, \oplus$ denotes the [bitwise XOR operation].)

JJ wants to make A equal to B.
Determine the minimum number of operations required to do so. Print -1 if it is not possible.

------ Input Format ------

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first and only line of each test case contains three integers A, B, and N — the parameters mentioned in the statement.

------ Output Format ------

For each test case, output the minimum number of operations required to make A equal to B. Output -1 if it is not possible to do so.

------ Constraints ------

$1 ≤ T ≤ 1000$
$0 ≤ A, B < 2^{30}$
$1 ≤ N ≤2^{30}$

------ subtasks ------

Subtask 1 (30 points): $N$ is a power of $2$.
Subtask 2 (70 points): Original Constraints.

----- Sample Input 1 ------
3
5 5 2
3 7 8
8 11 1

----- Sample Output 1 ------
0
1
-1

----- explanation 1 ------
- Test Case $1$: $A$ is already equal to $B$. Hence we do not need to perform any operation.
- Test Case $2$: We can perform the operation with $X = 4$ which is $< 8$. Therefore $A = 3 \oplus 4 = 7$. Thus, only one operation is required.
- Test Case $3$: We can show that it is not possible to make $A$ equal to $B$.

----- Sample Input 2 ------
2
24 27 3
4 5 1000

----- Sample Output 2 ------
2
1
----- explanation 2 ------
Note that the above sample case belongs to subtask $2$.

• Test Case 1: We can first perform the operation with $X = 1$ which is $< 3$. Therefore $A = 24 \oplus 1 = 25$. Then we can perform the operation with $X = 2$ which is $< 3$. Therefore $A = 25 \oplus 2 = 27$. Therefore we can make $A$ equal to $B$ in $2$ operations. It can be shown that it is not possible to do this in less than $2$ operations.

见题面

见题面