Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

B. Jellyfish and Math
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard 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.

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