← 返回题目列表

Codeforces · 1874/B

B. 水母和数学

中文机器翻译题面 查看原题

Jellyfish 被赋予非负整数 $$$a$$$、$$$b$$$、$$$c$$$、$$$d$$$ 和 $$$m$$$。最初 $$$(x,y)=(a,b)$$$。 Jellyfish 想要进行多项操作,以便 $$$(x,y)=(c,d)$$$。

对于每个操作,她可以执行以下操作之一:

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

这里$$$\&$$$表示按位AND运算,$$$|$$$表示按位OR运算,$$$\oplus$$$表示按位异或运算。

现在 Jellyfish 要求您输入满足 $$$(x,y)=(c,d)$$$ 的最少操作数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^5$$$)。测试用例的描述如下。

每个测试用例的唯一行包含五个整数,$$$a$$$、$$$b$$$、$$$c$$$、$$$d$$$ 和 $$$m$$$ ($$$0 \leq a, b, c, d, m < 2^{30}$$$)。

输出

对于每个测试用例,输出一个整数 - 最小操作数。如果无法实现,则输出 $$$-1$$$ 代替。

示例

输入 #1

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

输出 #1

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

注意

在第一个测试用例中,我们可以执行操作 $$$y = x \oplus y$$$。

在第二个测试用例中,不可能使用任何操作序列来更改 $$$(x,y)=(1,2)$$$。

在第三个测试用例中,我们可以执行操作 $$$x = x\,\&\,y$$$,然后执行操作 $$$y = y \oplus m$$$。