Language: C++

////////////////////
///   template   ///
////////////////////

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>
#include <complex>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
using namespace std;

//// MACRO ////
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i,n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i,s,n) for (int i = (s); i < (n); i++)
#define allof(c) c.begin(), c.end()
#define partof(c,i,n) c.begin() + (i), c.begin() + (i) + (n)
#define EPS 1e-10
#define INF 1000000000

#define countof(a) (sizeof(a)/sizeof(a[0]))
#define PREDIACTE(t,a) [](const t & a) -> bool
#define COMPARISON_T(t) bool(*)(const t &, const t &)
#define COMPARISON(t,a,b) [](const t & a, const t & b) -> bool

//// prime ////
vector<unsigned char> isPrime;
vector<int> primes;
void initPrimes(int n)
{
	isPrime = vector<unsigned char>(n + 1, true);
	isPrime[0] = isPrime[1] = false;
	FOR(i, 2, n + 1)
	{
		if (!isPrime[i]) continue;
		primes.push_back(i);
		for (int j = i * 2; j <= n; j += i)
			isPrime[j] = false;
	}
}

//// Probability ////

// パスカルの三角形(二項定理) 2種類の並べ替えにつかう。
vector<vector<double>> makePascalTriangle(int n, bool probability = false)
{
	typedef vector<double> VD;
	vector<VD> t;
	if (!t.size()) { t.push_back(VD(1, 1)); }
	FOR(i, t.size(), n + 1)
	{
		t.push_back(VD(i + 1));
		REP(j, i)
		{
			double x = t[i - 1][j] * (probability ? 0.5 : 1);
			t[i][j] += x;
			t[i][j + 1] += x;
		}
	}
	return t;
}


//// iota iterator ////
struct iotait
{
	int n;
	iotait(int n = 0) : n(n) { }
	iotait &operator ++() { ++n; return *this; }
	int operator *() { return n; }
};

//// geo ////
struct P3
{
	double x, y, z;
	P3(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) { }
	P3 operator +() const { return *this; }
	P3 operator +(const P3 &_) const { return P3(x + _.x, y + _.y, z + _.z); }
	P3 operator -() const { return P3(-x, -y, -z); }
	P3 operator -(const P3 &_) const { return *this + -_; }
	P3 operator *(double _) const { return P3(x*_, y*_, z*_); }
	P3 operator /(double _) const { return P3(x / _, y / _, z / _); }
	double dot(const P3 &_) const { return x*_.x + y*_.y + z*_.z; } // 内積
	P3 cross(const P3 &_) const { return P3(y*_.z - z*_.y, z*_.x - x*_.z, x*_.y - y*_.x); } // 外積
	double sqlength() const { return x*x + y*y + z*z; } // 二乗長さ
	double length() const { return sqrt(sqlength()); } // 長さ
	P3 direction() const { return *this / length(); } // 方向ベクトル
};

struct Sphere
{
	P3 c;
	double r;
	Sphere(double x, double y, double z, double r) : c(x, y, z), r(r) { }
	bool IntersectWith(const Sphere &rhs) { return (c - rhs.c).length() - (r + rhs.r) < EPS; } // 接してても真。
};

//// bit ////
#ifdef _MSC_VER
inline unsigned __builtin_ctz(unsigned x) { unsigned long r; _BitScanForward(&r, x); return r; }
#endif

inline int next_bit_permutation(int x)
{
	int t = x | (x - 1);
	return (t + 1) | (unsigned)((~t & -~t) - 1) >> (__builtin_ctz(x) + 1);
}

//// graph ////
struct Path
{
	int from;
	int to;
	double cost;
	Path(int from = 0, int to = 0, double cost = 0) : from(from), to(to), cost(cost) { }
	bool operator < (const Path &rhs) const { return cost < rhs.cost; }
	bool operator >(const Path &rhs) const { return cost > rhs.cost; }
};



// prim //
pair<double, vector<int>> prim(const vector<vector<double>> &costTable)
{
	int N = costTable.size();
	priority_queue<Path, vector<Path>, greater<Path>> q;
	q.push(Path(0, 0, 0));

	vector<int> parent(N, -1);
	double totalCost = 0;
	while (!q.empty())
	{
		Path cur = q.top(); q.pop();
		int i = cur.to;
		if (parent[i] != -1) continue;
		parent[i] = cur.from;
		totalCost += cur.cost;
		REP(j, N) if (parent[j] == -1) q.push(Path(i, j, costTable[i][j]));
	}
	return make_pair(totalCost, parent);
}

// dijkstra //
pair<vector<double>, vector<int>> dijkstra(const vector<vector<Path>> &routes, int start = 0, int goal = -1)
{
	int N = routes.size();
	priority_queue<Path, vector<Path>, greater<Path>> q;
	q.push(Path(start, start, 0));

	vector<int> prev(N, -1);
	vector<double> cost(N, INF);
	while (!q.empty())
	{
		Path cur = q.top(); q.pop();
		int i = cur.to;
		if (prev[i] != -1) continue;
		prev[i] = cur.from;
		cost[i] = cur.cost;
		if (i == goal) { break; }
		REP(j, routes[i].size())
		{
			Path next = Path(i, routes[i][j].to, cur.cost + routes[i][j].cost);
			if (prev[next.to] == -1)
				q.push(next);
		}
	}
	return make_pair(cost, prev);
}

//// i/o ////
template <class T>
class vevector : public vector<vector<T>>
{
public:
	vevector(int n = 0, int m = 0) : vector<vector<T>>(n, vector<T>(m)) { };
	vevector(int n, int m, const T &initial) : vector<vector<T>>(n, vector<T>(m, initial)) { };
};

template <class T> T read() { T t; cin >> t; return t; }
template <class T> vector<T> read(int n) { vector<T> v; REP(i, n) { v.push_back(read<T>()); } return v; }
template <class T> vevector<T> read(int n, int m) { vevector<T> v; REP(i, n) v.push_back(read<T>(m)); return v; }
template <class T> vevector<T> readjag(int n) { vevector<T> v; REP(i, n) v.push_back(read<T>(read<int>())); return v; }
template <class T> void write(const T &t) { cout << t << endl; }
template <class T> void write(const T &t, const T &t2) { cout << t << ' ' << t2 << endl; }
template <class T> void write(const vector<T> &v)
{
	ostringstream ss;
	for (auto x : v) ss << x << ' ';
	auto s = ss.str();
	cout << s.substr(0, s.length() - 1) << endl;
}

struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
#define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__

template <class InIt1, class InIt2>
int partial_compare(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2)
{
	return lexicographical_compare(first1, last1, first2, last2) ? -1
		: lexicographical_compare(first2, last2, first1, last1) ? 1
		: 0;
}

//// start up ////
void solve();
int main()
{
	// freopen("A.in", "r", stdin);
	solve();
	return 0;
}

////////////////////
/// template end ///
////////////////////

void dump(unsigned char *pv)
{
	REP(i, 4)
	{
		write(vector<int>(pv + i * 8, pv + i * 8 + 8));
	}
	write("");
}


void solve()
{
	int FREE = 0;

	union bd
	{
		unsigned char stt[32];
		unsigned long long ull[4];
		inline bool operator < (const bd &rhs) const { return lexicographical_compare(ull, ull + 4, rhs.ull, rhs.ull + 4); }
		inline bool operator ==(const bd &rhs) const { return equal(stt, stt + 32, rhs.stt); }
		static bd fromVector(const vector<int> &v) { bd r = {}; copy_n(v.begin(), 32, r.stt); return r; }
		struct hash { size_t operator() (const bd &b) { return b.ull[0] ^ b.ull[1] ^ b.ull[2] ^ b.ull[3]; } };
	};

	bd goal;
	{
		vector<int> goal_;
		FOR(i, 1, 5) { FOR(j, 1, 8) goal_.push_back(i * 10 + j); goal_.push_back(FREE); }
		goal = bd::fromVector(goal_);
	}

	auto testcases = read<int>();
	REP(testcase, testcases)
	{

		bd initial;
		{
			vector<int> table = read<int>(28);
			table.insert(table.begin() + 0, FREE);
			table.insert(table.begin() + 8, FREE);
			table.insert(table.begin() + 16, FREE);
			table.insert(table.begin() + 24, FREE);

			swap(*find(allof(table), 11), table[0]);
			swap(*find(allof(table), 21), table[8]);
			swap(*find(allof(table), 31), table[16]);
			swap(*find(allof(table), 41), table[24]);

			initial = bd::fromVector(table);
		}

		auto visited = unordered_set<bd, bd::hash>();
		
		int result = -1;

		struct Node { bd bd; int step; };
		queue<Node> q;
		q.push({ initial, 0 });
		while (!q.empty())
		{
			Node cur = q.front(); q.pop();
			if (visited.count(cur.bd) > 0) { continue; }
			visited.insert(cur.bd);
			//dump(cur.bd.stt);

			if (cur.bd == goal) { result = cur.step; break; }
			REP(i, 4)
			{
				bd next = cur.bd;
				auto it = next.stt;
				REP(j, i + 1) it = find(it + 1, next.stt + 32, FREE);
				auto it2 = find(next.stt, next.stt + 32, *(it - 1) + 1);
				if (it2 != next.stt + 32)
				{
					swap(*it, *it2);
					if (visited.count(next) == 0) q.push({ next, cur.step + 1 });
				}
			}
		}

		write(result);
	}

}

Compiler output:
a.cc: In function 'void solve()':
a.cc:287:34: error: declaration of 'solve()::bd solve()::Node::bd' changes meaning of 'bd' [-Wchanges-meaning]
  287 |                 struct Node { bd bd; int step; };
      |                                  ^~
a.cc:287:31: note: used here to mean 'union solve()::bd'
  287 |                 struct Node { bd bd; int step; };
      |                               ^~
a.cc:246:15: note: declared here
  246 |         union bd
      |               ^~
In file included from /usr/include/c++/14/bits/hashtable.h:35,
                 from /usr/include/c++/14/bits/unordered_map.h:33,
                 from /usr/include/c++/14/unordered_map:41,
                 from /usr/include/c++/14/functional:63,
                 from a.cc:12:
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code(const _Key&) const [with _Key = solve()::bd; _Value = solve()::bd; _ExtractKey = std::__detail::_Identity; _Hash = solve()::bd::hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; __hash_code = long unsigned int]':
/usr/include/c++/14/bits/hashtable.h:1763:46:   required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::const_iterator std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::find(const key_type&) const [with _Key = solve()::bd; _Value = solve()::bd; _Alloc = std::allocator<solve()::bd>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<solve()::bd>; _Hash = solve()::bd::hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; const_iterator = std::__detail::_Insert_base<solve()::bd, solve()::bd, std::allocator<solve()::bd>, std::__detail::_Identity, std::equal_to<solve()::bd>, solve()::bd::hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::const_iterator; key_type = solve()::bd]'
 1763 |       __hash_code __code = this->_M_hash_code(__k);
      |                            ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/14/bits/hashtable.h:1828:23:   required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::size_type std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::count(const key_type&) const [with _Key = solve()::bd; _Value = solve()::bd; _Alloc = std::allocator<solve()::bd>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<solve()::bd>; _Hash = solve()::bd::hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; size_type = long unsigned int; key_type = solve()::bd]'
 1828 |       auto __it = find(__k);
      |                   ~~~~^~~~~
/usr/include/c++/14/bits/unordered_set.h:693:26:   required from 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type std::unordered_set<_Value, _Hash, _Pred, _Alloc>::count(const key_type&) const [with _Value = solve()::bd; _Hash = solve()::bd::hash; _Pred = std::equal_to<solve()::bd>; _Alloc = std::allocator<solve()::bd>; size_type = long unsigned int; key_type = solve()::bd]'
  693 |       { return _M_h.count(__x); }
      |                ~~~~~~~~~~^~~~~
a.cc:293:21:   required from here
  293 |                         if (visited.count(cur.bd) > 0) { continue; }
      |                             ~~~~~~~~~~~~~^~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1335:23: error: static assertion failed: hash function must be invocable with an argument of key type
 1335 |         static_assert(__is_invocable<const _Hash&, const _Key&>{},
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1335:23: note: 'std::__is_invocable<const solve()::bd::hash&, const solve()::bd&>()' evaluates to false
/usr/include/c++/14/bits/hashtable_policy.h:1337:25: error: no match for call to '(const solve()::bd::hash) (const solve()::bd&)'
 1337 |         return _M_hash()(__k);
      |                ~~~~~~~~~^~~~~
a.cc:253:38: note: candidate: 'size_t solve()::bd::hash::operator()(const solve()::bd&)' (near match)
  253 |                 struct hash { size_t operator() (const bd &b) { return b.ull[0] ^ b.ull[1] ^ b.ull[2] ^ b.ull[3]; } };
      |                                      ^~~~~~~~
a.cc:253:38: note:   passing 'const solve()::bd::hash*' as 'this' argument discards qualifiers
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code_tr(const _Kt&) const [with _Kt = solve()::bd; _Key = solve()::bd; _Value = solve()::bd; _ExtractKey = std::__detail::_Identity; _Hash = solve()::bd::hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; __hash_code = long unsigned int]':
/usr/include/c++/14/bits/hashtable.h:2329:44:   required from 'std::pair<typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator, bool> std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&) [with _Kt = const solve()::bd&; _Arg = const solve()::bd&; _NodeGenerator = std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<solve()::bd, true> > >; _Key = solve()::bd; _Value = solve()::bd; _Alloc = std::allocator<solve()::bd>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<solve()::bd>; _Hash = solve()::bd::hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator = std::__detail::_Insert_base<solve()::bd, solve()::bd, std::allocator<solve()::bd>, std::__detail::_Identity, std::equal_to<solve()::bd>, solve()::bd::hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; typename _Traits::__constant_iterators = std::__detail::_Hashtable_traits<true, true, true>::__constant_iterators]'
 2329 |         __hash_code __code = this->_M_hash_code_tr(__k);
      |                              ~~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/14/bits/hashtable.h:947:27:   required from 'std::pair<typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator, bool> std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_M_insert_unique_aux(_Arg&&, const _NodeGenerator&) [with _Arg = const solve()::bd&; _NodeGenerator = std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<solve()::bd, true> > >; _Key = solve()::bd; _Value = solve()::bd; _Alloc = std::allocator<solve()::bd>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<solve()::bd>; _Hash = solve()::bd::hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator = std::__detail::_Insert_base<solve()::bd, solve()::bd, std::allocator<solve()::bd>, std::__detail::_Identity, std::equal_to<solve()::bd>, solve()::bd::hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >::iterator; typename _Traits::__constant_iterators = std::__detail::_Hashtable_traits<true, true, true>::__constant_iterators]'
  947 |           return _M_insert_unique(
      |                  ~~~~~~~~~~~~~~~~^
  948 |             _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  949 |             std::forward<_Arg>(__arg), __node_gen);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable.h:959:31:   required from 'std::pair<typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator, bool> std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_M_insert(_Arg&&, const _NodeGenerator&, std::true_type) [with _Arg = const solve()::bd&; _NodeGenerator = std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<solve()::bd, true> > >; _Key = solve()::bd; _Value = solve()::bd; _Alloc = std::allocator<solve()::bd>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<solve()::bd>; _Hash = solve()::bd::hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; typename std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal