看到这种操作乱七八糟不能直接算的题，可以考虑最短路。
对于 \(a, b, c, d, m\) 按位考虑，发现相同的 \((a, b, m)\) 无论如何操作必然还是相同的。
于是考虑对于每个可能的 \((0/1, 0/1, 0/1)\)，所有终态有 \((c = 0/1, d = 0/1)\) 或者不确定。这样我们对于一组询问，可以压缩成一个状态，而本质不同状态有 \(5^8\) 种。预处理一下最短路即可。然后对于不确定的位，预处理的时候枚举它是什么即可。
时间复杂度 \(O(5^8 + t \log V)\)。
code
// Problem: B. Jellyfish and Math
// Contest: Codeforces - Codeforces Round 901 (Div. 1)
// URL: https://codeforces.com/contest/1874/problem/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 400000;
const int pw[] = {1, 5, 25, 125, 625, 3125, 15625, 78125, 390625};
inline int calc1(int a, int b, int m) {
return (a << 2) | (b << 1) | m;
}
inline int calc2(int c, int d) {
return (c << 1) | d;
}
int f[maxn];
inline void init() {
mems(f, -1);
queue<int> q;
int S = 0;
for (int a = 0; a <= 1; ++a) {
for (int b = 0; b <= 1; ++b) {
for (int m = 0; m <= 1; ++m) {
S += pw[calc1(a, b, m)] * calc2(a, b);
}
}
}
f[S] = 0;
q.push(S);
while (q.size()) {
int u = q.front();
q.pop();
int v = 0;
for (int a = 0; a <= 1; ++a) {
for (int b = 0; b <= 1; ++b) {
for (int m = 0; m <= 1; ++m) {
int _ = u / pw[calc1(a, b, m)] % 5;
int x = (_ >> 1), y = (_ & 1);
x = x & y;
v += pw[calc1(a, b, m)] * calc2(x, y);
}
}
}
if (f[v] == -1) {
f[v] = f[u] + 1;
q.push(v);
}
v = 0;
for (int a = 0; a <= 1; ++a) {
for (int b = 0; b <= 1; ++b) {
for (int m = 0; m <= 1; ++m) {
int _ = u / pw[calc1(a, b, m)] % 5;
int x = (_ >> 1), y = (_ & 1);
x = x | y;
v += pw[calc1(a, b, m)] * calc2(x, y);
}
}
}
if (f[v] == -1) {
f[v] = f[u] + 1;
q.push(v);
}
v = 0;
for (int a = 0; a <= 1; ++a) {
for (int b = 0; b <= 1; ++b) {
for (int m = 0; m <= 1; ++m) {
int _ = u / pw[calc1(a, b, m)] % 5;
int x = (_ >> 1), y = (_ & 1);
y = x ^ y;
v += pw[calc1(a, b, m)] * calc2(x, y);
}
}
}
if (f[v] == -1) {
f[v] = f[u] + 1;
q.push(v);
}
v = 0;
for (int a = 0; a <= 1; ++a) {
for (int b = 0; b <= 1; ++b) {
for (int m = 0; m <= 1; ++m) {
int _ = u / pw[calc1(a, b, m)] % 5;
int x = (_ >> 1), y = (_ & 1);
y = y ^ m;
v += pw[calc1(a, b, m)] * calc2(x, y);
}
}
}
if (f[v] == -1) {
f[v] = f[u] + 1;
q.push(v);
}
}
for (int S = 0; S < pw[8]; ++S) {
for (int i = 0; i < 8; ++i) {
if (S / pw[i] % 5 == 4) {
int mn = 1e9;
for (int j = 0; j < 4; ++j) {
int T = S - (4 - j) * pw[i];
mn = min(mn, f[T] == -1 ? (int)1e9 : f[T]);
}
f[S] = mn > 1e8 ? -1 : mn;
break;
}
}
}
}
int p[9];
void solve() {
for (int i = 0; i < 8; ++i) {
p[i] = 4;
}
int A, B, C, D, M;
scanf("%d%d%d%d%d", &A, &B, &C, &D, &M);
for (int i = 0; i < 30; ++i) {
int a = (A >> i) & 1, b = (B >> i) & 1, c = (C >> i) & 1, d = (D >> i) & 1, m = (M >> i) & 1;
if (p[calc1(a, b, m)] == 4) {
p[calc1(a, b, m)] = calc2(c, d);
} else if (p[calc1(a, b, m)] != calc2(c, d)) {
puts("-1");
return;
}
}
int S = 0;
for (int i = 0; i < 8; ++i) {
S += pw[i] * p[i];
}
printf("%d\n", f[S]);
}
int main() {
init();
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}