#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; #define ppf pop_front #define ppb pop_back #define pf push_front #define pb push_back #define fr first #define sc second #define mnto(x,y) x = min(x, (__typeof__(x))y) #define mxto(x,y) x = max(x, (__typeof__(x))y) #define setval(arr, x) memset(arr, x, sizeof(arr)) template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; static const int MAXN = 8; static int fact[MAXN+1]; static vector<vector<int>> distv(MAXN+1); int lehmer(const vector<int> &p) { int N = p.size(); int code = 0; for (int i = 0; i < N; ++i) { int cnt = 0; for (int j = i+1; j < N; ++j) if (p[j] < p[i]) cnt++; code += cnt * fact[N-i-1]; } return code; } void precompute() { fact[0] = 1; for (int i = 1; i <= MAXN; ++i) fact[i] = fact[i-1] * i; for (int N = 1; N <= MAXN; ++N) { int total = fact[N]; distv[N].assign(total, -1); vector<int> target(N); for (int i = 0; i < N; ++i) target[i] = N-i-1; int start = lehmer(target); queue<vector<int>> q; q.push(target); distv[N][start] = 0; while (!q.empty()) { auto cur = q.front(); q.pop(); int d = distv[N][lehmer(cur)]; for (int i = 0; i < N; ++i) { auto nxt = cur; reverse(nxt.begin()+i, nxt.end()); int code = lehmer(nxt); if (distv[N][code] == -1) { distv[N][code] = d+1; q.push(nxt); } } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); precompute(); int T; cin >> T; while (T--) { int N; cin >> N; vector<ll> a(N); for (int i = 0; i < N; ++i) cin >> a[i]; vector<ll> sorted = a; sort(sorted.begin(), sorted.end()); unordered_map<ll, int> rank; for (int i = 0; i < N; ++i) rank[sorted[i]] = i; vector<int> p(N); for (int i = 0; i < N; ++i) p[i] = rank[a[i]]; int code = lehmer(p); cout << distv[N][code] << '\n'; } }