A16219 | Jellyfish and Math

Jellyfish is given the non-negative integers $a$ , $b$ , $c$ , $d$ and $m$ . Initially $(x,y)=(a,b)$ . Jellyfish wants to do several operations so that $(x,y)=(c,d)$ .

For each operation, she can do one of the following:

- $x := x\,\&\,y$ ,
- $x := x\,|\,y$ ,
- $y := x \oplus y$ ,
- $y := y \oplus m$ .

Here $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND), $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR) and $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

Now Jellyfish asks you for the minimum number of operations such that $(x,y)=(c,d)$ .

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \leq t \leq 10^5$ ). The description of the test cases follows.

The only line of each test case contains five integers, $a$ , $b$ , $c$ , $d$ and $m$ ( $0 \leq a, b, c, d, m < 2^{30}$ ).

For each test case, output a single integer — the minimum number of operations. If this cannot be achieved, output $-1$ instead.