Vanya has learned about XOR and now presses this button on his calculator whenever he gets the chance. The screen currently shows $$$a$$$, but Vanya wants it to show $$$b$$$. Unfortunately, his calculator is rather stubborn: it only lets him XOR with integers from zero to $$$k$$$, inclusive.
In one move, Vanya chooses an integer $$$x$$$ ($$$0 \le x \le k$$$) and replaces the number $$$a$$$ on the screen with $$$a \oplus x$$$. Here, $$$\oplus$$$ denotes XOR.
To compute the XOR of two non-negative integers, write them in binary. If their representations have different lengths, add leading zeros to the shorter one. Each bit of the result is one if the corresponding bits of the two integers differ, and zero if they are equal. For example, five and three are written as $$$101$$$ and $$$011$$$ in binary, so their XOR is $$$110$$$, which is six.
Determine the minimum number of moves Vanya needs to obtain $$$b$$$, or report that this is impossible.
The first line contains an integer $$$t$$$ — the number of test cases ($$$1 \le t \le 10^4$$$).
Each of the following $$$t$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$k$$$ ($$$0 \le a, b, k \le 10^9$$$).
For each test case, output one integer: the minimum number of moves needed to make $$$a$$$ equal to $$$b$$$, or $$$-1$$$ if this is impossible.
6 5 5 0 5 2 7 0 7 4 0 8 7 3 4 0 8 9 1
0 1 2 -1 -1 1
In the first test case, $$$a$$$ is already equal to $$$b$$$, so no moves are needed.
In the second test case, choose $$$x = 7$$$: $$$5 \oplus 7 = 2$$$.
In the third test case, two moves suffice: $$$0 \oplus 4 = 4$$$, then $$$4 \oplus 3 = 7$$$. One move cannot suffice because $$$7 \gt k$$$.
In the fourth test case, every allowed $$$x$$$ is less than eight, so no move can change the bit corresponding to eight.
In the fifth test case, the only allowed value is $$$x = 0$$$, which leaves $$$a$$$ unchanged.
In the sixth test case, choose $$$x = 1$$$: $$$8 \oplus 1 = 9$$$.