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$$$。