#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
    int ttt;
    cin>>ttt;
    random_device seed;
    mt19937 rnd(seed());
    while(ttt--){
        int n;
        cin>>n;
        vector<vector<int>> a(n,vector<int>(n));
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j],a[i][j]--;

        vector<int> ans;
        auto fr=[&](int r)->void{
            ans.push_back(r+1);
            reverse(a[r].begin(),a[r].end());
        };
        auto fc=[&](int c)->void{
            ans.push_back(c+1);
            vector<int> tmp(n);
            for(int i=0;i<n/2;i++)swap(a[i][c],a[n-i-1][c]);
        };

        vector<vector<int>> sign(n,vector<int>(n));
        {
            if(n%2==1){
                vector<int> r(n),c(n);
                vector<int> rr(n),cc(n);
                for(int i=0;i<n;i++){
                    r[i]=a[n/2][i];
                    rr[i]=(n/2)*n+i;
                    c[i]=a[i][n/2];
                    cc[i]=i*n+(n/2);
                }
                vector<int> revr=rr,revc=cc;
                reverse(revr.begin(),revr.end());
                reverse(revc.begin(),revc.end());
                //for(int x:r)cout<<x<<" ";
               // out<<endl;
                //for(int x:rr)cout<<x<<" ";
                //cout<<endl;
                //for(int x:revr)cout<<x<<" ";
                //cout<<endl;
                //for(int x:c)cout<<x<<" ";
                //cout<<endl;
                //for(int x:cc)cout<<x<<" ";
                //cout<<endl;
                //for(int x:revc)cout<<x<<" ";
                //cout<<endl;
                if(r==rr&&c==cc){
                }else if(r==revr&&c==cc){
                    fr(n/2);
                    fc(0);
                }else if(r==rr&&c==revc){
                    fr(n/2);
                    fc(n/2);
                    fr(n/2);
                    fc(0);
                }else if(r==revr&&c==revc){
                    fr(n/2);
                    fc(n/2);
                }else {
                    cout<<-1<<endl;
                    continue;
                }
            }

            //for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
                 

            bool ok=true;
            for(int i=0;i<n/2;i++)for(int j=0;j<n/2;j++){
                vector<int> x,y;
                x.push_back(i*n+j);y.push_back(a[i][j]);
                x.push_back(i*n+(n-j-1));y.push_back(a[i][n-j-1]);
                x.push_back((n-i-1)*n+j);y.push_back(a[n-i-1][j]);
                x.push_back((n-i-1)*n+(n-j-1));y.push_back(a[n-i-1][n-j-1]);
                auto z=y;
                sort(z.begin(),z.end());
                if(x!=z){
                    ok=false;
                }else{
                    int cnt=0;
                    for(int s=0;s<4;s++)for(int t=s+1;t<4;t++)if(y[s]>y[t])cnt++;
                    for(int t:x)sign[t/n][t%n]=1-2*(cnt%2);
                    
                }
            }
            //for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<sign[i][j]<<(j+1==n?"\n":" ");
            vector<int> rs,cs;
            for(int i=0;i<n/2;i++){
                if(sign[0][i]==-1){
                    cs.push_back(i);
                    for(int j=0;j<n/2;j++)sign[j][i]*=-1;
                }
            }
            for(int i=1;i<n/2;i++){
                set<int> s;
                for(int j=0;j<n/2;j++){
                    s.insert(sign[i][j]);
                }
                //cout<<s.size()<<endl;
                if(s.size()==2)ok=false;
                else if((*s.begin())==-1){
                    rs.push_back(i);
                    for(int j=0;j<n/2;j++)sign[i][j]=1;
                }
            }
            if(!ok){
                cout<<-1<<endl;
                continue;
            }
            while(cs.size()+rs.size()){
                if(cs.size()&&rs.size()){
                    fr(rs.back());
                    fc(cs.back());
                    rs.pop_back();
                    cs.pop_back();
                }else if(cs.size()){
                    fr(0);
                    fc(cs.back());
                    cs.pop_back();
                    fr(0);
                    if(!cs.empty()){
                        fc(cs.back());
                        cs.pop_back();
                    }
                }else if(rs.size()){
                    fr(rs.back());
                    rs.pop_back();
                    if(!rs.empty()){
                        fc(0);
                        fr(rs.back());
                        rs.pop_back();
                        fc(0);
                    }
                }
            }

            //for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
        }
        vector<int> todo;
        for(int i=0;i<n/2;i++)for(int j=0;j<n/2;j++)todo.push_back(i*n+j);
        for(int i=0;i<todo.size();i++){
            int r=rnd()%(todo.size()-i);
            swap(todo[r],todo[todo.size()-1-i]);
        }
        auto rotate=[&](int x,int y)->void{
            if(ans.size()%2==0){
                fr(n-x-1);
                fc(n-y-1);
                fr(n-x-1);
                fc(n-y-1);
            }else{
                fc(n-y-1);
                fr(n-x-1);
                fc(n-y-1);
                fr(n-x-1);
            }
        };
        for(int r:todo){
            //cout<<"do"<<r<<endl;
            int x=r/n,y=r%n;
            if(a[x][y]!=x*n+y&&a[n-x-1][y]!=(n-x-1)*n+y&&a[x][n-y-1]!=x*n+(n-y-1)&&a[n-x-1][n-y-1]!=(n-x-1)*n+(n-y-1)){
                rotate(x,y);
                //cout<<"rotated"<<endl;

                //for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
            }
            if(a[x][y]==x*n+y&&a[n-x-1][y]==(n-x-1)*n+y&&a[x][n-y-1]==x*n+(n-y-1)&&a[n-x-1][n-y-1]==(n-x-1)*n+(n-y-1)){
                continue;
            }
            if(a[x][y]==x*n+y){
                rotate(x,y);
                if(a[n-x-1][y]!=(n-x-1)*n+y)rotate(x,y);
            }else if(a[n-x-1][y]==(n-x-1)*n+y){
                rotate(n-x-1,y);
                if(a[x][y]!=x*n+y)rotate(n-x-1,y);
            }else if(a[x][n-y-1]==x*n+(n-y-1)){
                rotate(x,n-y-1);
                if(a[x][y]!=x*n+y)rotate(x,n-y-1);
            }else if(a[n-x-1][n-y-1]==(n-x-1)*n+(n-y-1)){
                rotate(n-x-1,n-y-1);
                if(a[x][y]!=x*n+y)rotate(n-x-1,n-y-1);
            }
            
            //for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
        }

        cout<<ans.size()<<endl;
        for(int i=0;i<ans.size();i++){
            cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
        }

        vector<vector<int>> ca(n,vector<int>(n));
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)ca[i][j]=i*n+j;
        //for(int i=0;i<n;i++)for(int j=0;j<n;j++)cout<<a[i][j]<<(j+1==n?"\n":" ");
        assert(ca==a);
        assert(ans.size()<=4*n*n);


    }
}