B. Медуза и математика
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Медузе даны целые неотрицательные числа $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ и $$$m$$$. Первоначально $$$(x,y)=(a,b)$$$. Медуза хочет выполнить несколько операций так, чтобы получилось $$$(x,y)=(c,d)$$$.

Одна операция заключается в выполенении одного из следующих действий:

  • $$$x := x\,\&\,y$$$,
  • $$$x := x\,|\,y$$$,
  • $$$y := x \oplus y$$$,
  • $$$y := y \oplus m$$$.

Здесь $$$\&$$$ обозначает побитовую операцию И, $$$|$$$ обозначает побитовую операцию ИЛИ, $$$\oplus$$$ обозначает побитовое исключающее ИЛИ.

Медуза хочет узнать минимальное количество операций, после которого можно получить $$$(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$$$.

Пример
Входные данные
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
2
-1
-1
2
1
4
1
3
Примечание

В первом наборе входных данных мы можем выполнить операцию $$$y = x \oplus y$$$.

Во втором наборе входных данных получить $$$(x,y)=(1,2)$$$ с помощью какой-либо последовательности операций невозможно.

В третьем наборе входных данных можно выполнить операцию $$$x = x\,\&\,y$$$, а после $$$y = y \oplus m$$$.