#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<(a)<<endl
#define dumparr(a,n) cerr<<#a<<"["<<(n)<<"]="<<(a[n])<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

pll operator+(pll a,pll b){
  return pll(a.first+b.first,a.second+b.second);
}
pll operator-(pll a,pll b){
  return pll(a.first-b.first,a.second-b.second);
}
pll operator*(ll a,pll b){
  return pll(b.first*a,b.second*a);
}
const ll INF=(1LL<<60);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  a=abs(a);
  b=abs(b);
  if(a==0)return b;
  if(b==0)return a;
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(long long R, long long C, std::vector<std::vector<long long>> A, std::vector<std::vector<long long>> B){
  vector<vector<pll>> graph(R*C);
  auto id2pair = [C](ll x){
    return pll(x/C,x%C);
  };
  auto pair2id = [C](pll x){
    return x.first*C+x.second;
  };
  For(ii,R*C){
    auto [x,y] = id2pair(ii);
    if(y>0){
      auto jj = pair2id(pll(x,y-1));
      graph[ii].push_back(pll(jj,A[x][y-1]));
      graph[jj].push_back(pll(ii,A[x][y-1]));
    }
    if(x<R-1){
      auto jj = pair2id(pll(x+1,y));
      graph[ii].push_back(pll(jj,B[x][y]));
      graph[jj].push_back(pll(ii,2));
    }
  }
  priority_queue<tuple<ll,ll,ll>,vector<tuple<ll,ll,ll>>,greater<tuple<ll,ll,ll>>> q;
  q.push(make_tuple(0LL,0LL,-INF));
  vector<ll> distances(R*C,INF);
  vector<bool> fromxp1(R*C,false);
  distances[0]=0;
  while(!q.empty()){
    auto [curdist,cur,pre] = q.top();q.pop();
    auto [curx,cury]=id2pair(cur);
    auto [prex,prey]=id2pair(pre);
    for (auto [next,dist] : graph[cur])
    {
      auto [nextx,nexty]=id2pair(next);
      if(curx+1==prex&&nextx+1==curx){
        --dist;
      }
      if(distances[next]>curdist+dist){
        distances[next]=curdist+dist;
        q.emplace(curdist+dist,next,cur);
      }
      if(distances[next]==curdist+dist&&nextx+1==curx&&fromxp1[next]==false){
        fromxp1[next]=true;
        q.emplace(curdist+dist,next,cur);
      }
    }
  }
  cout<<distances[R*C-1]<<endl;
}

int main(){
  cout<<setprecision(1000);
  long long R;
    scanf("%lld",&R);
    long long C;
    scanf("%lld",&C);
    std::vector<std::vector<long long>> A(R, std::vector<long long>(C-1));
    for(int i = 0 ; i < R ; i++){
        for(int j = 0 ; j < C-1 ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    std::vector<std::vector<long long>> B(R-1, std::vector<long long>(C));
    for(int i = 0 ; i < R-1 ; i++){
        for(int j = 0 ; j < C ; j++){
            scanf("%lld",&B[i][j]);
        }
    }
  solve(R, C, std::move(A), std::move(B));
  return 0;
}

#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
// #include <atcoder/all>

using namespace std;
 
using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vii = V<int>;
using vvll = V<vll>;
using vvii = V< V<int> >;
using PII = P<int, int>;
using PLL = P<ll, ll>;
#define RevREP(i,n,a) for(ll i=n;i>a;i--)  // (a,n]
#define REP(i,a,n) for(ll i=a;i<n;i++)  // [a,n)
#define rep(i, n) REP(i,0,n)
#define ALL(v) v.begin(),v.end()
#define eb emplace_back
#define pb push_back
#define sz(v) int(v.size())
 
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
template< class A, class B > ostream& operator <<(ostream& out, const P<A, B> &p) {
    return out << '(' << p.first << ", " << p.second << ')';
}
template< class A > ostream& operator <<(ostream& out, const V<A> &v) {
    out << '[';
    for (int i=0;i<int(v.size());i++) {
        if (i) out << ", ";
        out << v[i];
    }
    return out << ']';
}
 
template<class A, class B> istream& operator >>(istream& in, P<A, B> &p) {
    return in >> p.first >> p.second;
}
template<class A> istream& operator >>(istream& in, V<A> &v) {
    for (int i = 0; i < int(v.size()); i++) in >> v[i];
    return in;
}

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t-->0) {
        int n; cin >> n;
        vii p(n);
        cin >> p;

        if (n == 2) {
            if (p[0] > p[1]) {
                cout << 1 << '\n';
                cout << 1 << '\n';
            } else {
                cout << 0 << '\n';
                cout << '\n';
            }
            continue;
        }

        vii ans;
        for (int tor = n; tor > 3; tor--) {
            int j = 1;
            for (; j <= n; j++) if (p[j - 1] == tor) break;
            if (j == tor) continue;
            if (sz(ans) & 1) {  // guusuu kaime
                if (j & 1) {
                    if (j == 1) {
                        ans.eb(j + 1), swap(p[j], p[j + 1]);
                    } else {
                        ans.eb(j - 1), swap(p[j - 2], p[j - 1]);
                        ans.eb(j), swap(p[j - 1], p[j]);
                        j--;
                    }
                }
                for (int k = j; k < tor; k++) {
                    ans.eb(k);
                    swap(p[k - 1], p[k]);
                }
            } else {  // kisuu kaime
                if (!(j & 1)) {
                    ans.eb(j - 1), swap(p[j - 2], p[j - 1]);
                    ans.eb(j), swap(p[j - 1], p[j]);
                    j--;
                }
                for (int k = j; k < tor; k++) {
                    ans.eb(k);
                    swap(p[k - 1], p[k]);
                }
            }
        }
        cerr << p << '\n';
        
        while (!(p[0] == 1 and p[1] == 2 and p[2] == 3)) {
            if (sz(ans) & 1) {
                ans.eb(2);
                swap(p[1], p[2]);
            } else {
                ans.eb(1);
                swap(p[0], p[1]);
            }
        }

        cout << sz(ans) << '\n';
        rep(i, sz(ans)) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}