310718: CF1875E. Jellyfish and Math

E. Jellyfish and Mathtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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, $|$ denotes the bitwise OR operation and $\oplus$ denotes the bitwise XOR operation.

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

Input

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}$).

Output

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

ExampleInput

10
1 0 1 1 1
3 3 1 2 1
1 6 0 7 1
2 4 4 9 8
21 4 0 17 28
50 50 0 0 39
95 33 1 33 110
138 202 174 64 108
78 340 68 340 461
457 291 491 566 766

Output

1
-1
2
-1
-1
2
1
4
1
3

Note

In the first test case, we can do the operation $y = x \oplus y$.

In the second test case, it is not possible to change $(x,y)=(1,2)$ using any sequence of operations.

In the third test case, we can do the operation $x = x\,\&\,y$ followed by the operation $y = y \oplus m$.

**题目大意：**
海蜇鱼获得了非负整数 $ a $, $ b $, $ c $, $ d $ 和 $ m $。初始时，坐标为 $ (x, y) = (a, b) $。海蜇鱼想要通过一系列操作使得坐标变为 $ (c, d) $。

每一步操作，她可以选择以下四种操作之一：
1. $ x := x \& y $（按位与操作）
2. $ x := x | y $（按位或操作）
3. $ y := x \oplus y $（按位异或操作）
4. $ y := y \oplus m $（按位异或操作，其中 $ m $ 是给定的整数）

要求计算最少需要多少步操作才能从 $ (a, b) $ 转换到 $ (c, d) $，如果不能实现，则输出 -1。

**输入数据格式：**
输入包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $），表示测试用例的数量。接下来每行包含五个整数 $ a $, $ b $, $ c $, $ d $ 和 $ m $（$ 0 \leq a, b, c, d, m < 2^{30} $），代表每个测试用例的初始坐标和目标坐标以及操作数 $ m $。

**输出数据格式：**
对于每个测试用例，输出一个整数，表示最少需要的操作次数。如果不能实现目标坐标，则输出 -1。

**示例：**
```
Input
10
1 0 1 1 1
3 3 1 2 1
1 6 0 7 1
2 4 4 9 8
21 4 0 17 28
50 50 0 0 39
95 33 1 33 110
138 202 174 64 108
78 340 68 340 461
457 291 491 566 766

Output
1
-1
2
-1
-1
2
1
4
1
3
```

**注意：**
- 第一个测试用例可以通过一次操作 $ y = x \oplus y $ 实现。
- 第二个测试用例无法通过任何操作序列从 $ (1,2) $ 转换到目标坐标。
- 第三个测试用例可以通过先进行操作 $ x = x \& y $ 然后进行操作 $ y = y \oplus m $ 来实现。**题目大意：** 海蜇鱼获得了非负整数 $ a $, $ b $, $ c $, $ d $ 和 $ m $。初始时，坐标为 $ (x, y) = (a, b) $。海蜇鱼想要通过一系列操作使得坐标变为 $ (c, d) $。 每一步操作，她可以选择以下四种操作之一： 1. $ x := x \& y $（按位与操作） 2. $ x := x | y $（按位或操作） 3. $ y := x \oplus y $（按位异或操作） 4. $ y := y \oplus m $（按位异或操作，其中 $ m $ 是给定的整数） 要求计算最少需要多少步操作才能从 $ (a, b) $ 转换到 $ (c, d) $，如果不能实现，则输出 -1。 **输入数据格式：** 输入包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $），表示测试用例的数量。接下来每行包含五个整数 $ a $, $ b $, $ c $, $ d $ 和 $ m $（$ 0 \leq a, b, c, d, m < 2^{30} $），代表每个测试用例的初始坐标和目标坐标以及操作数 $ m $。 **输出数据格式：** 对于每个测试用例，输出一个整数，表示最少需要的操作次数。如果不能实现目标坐标，则输出 -1。 **示例：** ``` Input 10 1 0 1 1 1 3 3 1 2 1 1 6 0 7 1 2 4 4 9 8 21 4 0 17 28 50 50 0 0 39 95 33 1 33 110 138 202 174 64 108 78 340 68 340 461 457 291 491 566 766 Output 1 -1 2 -1 -1 2 1 4 1 3 ``` **注意：** - 第一个测试用例可以通过一次操作 $ y = x \oplus y $ 实现。 - 第二个测试用例无法通过任何操作序列从 $ (1,2) $ 转换到目标坐标。 - 第三个测试用例可以通过先进行操作 $ x = x \& y $ 然后进行操作 $ y = y \oplus m $ 来实现。