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

其中 $\&$ 表示按位与运算，$|$ 表示按位或运算，$\oplus$ 表示按位异或运算。

现在 Jellyfish 请你求出使得 $(x,y)=(c,d)$ 所需的最少操作次数。如果无法达到目标，则输出 $-1$。

输入

每个测试点包含多个测试用例。第一行包含测试用例的数量 $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

Note

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

在第二个测试用例中，无法通过任何操作序列将 $(x,y)$ 变为 $(1,2)$。

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