/**
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡖⠁⠀⠀⠀⠀⠀⠀⠈⢲⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣼⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣧⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣸⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣇⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣿⣿⡇⠀⢀⣀⣤⣤⣤⣤⣀⡀⠀⢸⣿⣿⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⣔⢿⡿⠟⠛⠛⠻⢿⡿⣢⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣀⣤⣶⣾⣿⣿⣿⣷⣤⣀⡀⢀⣀⣤⣾⣿⣿⣿⣷⣶⣤⡀⠀⠀⠀⠀
⠀⠀⢠⣾⣿⡿⠿⠿⠿⣿⣿⣿⣿⡿⠏⠻⢿⣿⣿⣿⣿⠿⠿⠿⢿⣿⣷⡀⠀⠀
⠀⢠⡿⠋⠁⠀⠀⢸⣿⡇⠉⠻⣿⠇⠀⠀⠸⣿⡿⠋⢰⣿⡇⠀⠀⠈⠙⢿⡄⠀
⠀⡿⠁⠀⠀⠀⠀⠘⣿⣷⡀⠀⠰⣿⣶⣶⣿⡎⠀⢀⣾⣿⠇⠀⠀⠀⠀⠈⢿⠀
⠀⡇⠀⠀⠀⠀⠀⠀⠹⣿⣷⣄⠀⣿⣿⣿⣿⠀⣠⣾⣿⠏⠀⠀⠀⠀⠀⠀⢸⠀
⠀⠁⠀⠀⠀⠀⠀⠀⠀⠈⠻⢿⢇⣿⣿⣿⣿⡸⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠈⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠐⢤⣀⣀⢀⣀⣠⣴⣿⣿⠿⠋⠙⠿⣿⣿⣦⣄⣀⠀⠀⣀⡠⠂⠀⠀⠀
⠀⠀⠀⠀⠀⠈⠉⠛⠛⠛⠛⠉⠀⠀⠀⠀⠀⠈⠉⠛⠛⠛⠛⠋⠁⠀⠀
**/
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define nl cout<<"\n";
#define ll long long int
#define ld double
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define F(i,a,b) for(i=a;i<b;i++)
//#include <ext/pb_ds/assoc_container.hpp> // policy based data structure header files
//#include <ext/pb_ds/tree_policy.hpp> // policy based data structure header files
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
//using namespace __gnu_pbds; // for pbds
//#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> // have functions like order_of_key, find_by_order
const double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781641;
const ll M=1e9+7;
const ll MAXN=100200;
ll i,j,mask;
ll mod(ll x)
{
    return (x+M)%M;
}
ll add(ll a,ll b)
{
    return mod(mod(a)+mod(b));
}
ll mul(ll a,ll b)
{
    return mod(mod(a)*mod(b));
}
ll power(ll p,ll x)
{
    ll res=1;
    while(x>0) {
        if(x%2==1) {
            res=mul(res,p);
        }
        x/=2;
        p=mul(p,p);
    }
    return res;
}
void solve()
{
    ll n;
    cin>>n;
    ll sumMinus=0, sumPlus=0;
    vector<ll> v(n);
    F(i,0,n) {
        cin>>v[i];
    }
    if(n==1) {
        cout<<v[0];
    } else {
        sumMinus=add(v[0], -v[1]);
        sumPlus=add(v[0], v[1]);
        ll cntPlus=1;
        ll cntMinus=1;
        F(i,2,n) {
            ll mn=add(sumPlus, mul(-1,mul(v[i], cntPlus)) );
            ll mx=add(sumPlus, mul(cntPlus, v[i]) );
            mx=add(mx, add(sumMinus, mul(cntMinus, v[i]) ));
            sumMinus=mn;
            sumPlus=mx;
            ll tmp=cntPlus;
            cntPlus=add(cntPlus, cntMinus);
            cntMinus=tmp;
            //cout<<sumMinus<<" "<<sumPlus;nl
        }
//        nl
//        cout<<sumMinus<<" "<<sumPlus;nl
        ll ans=add(sumMinus, sumPlus);
        cout<<ans;
    }
}
int main()
{
    IOS
    /*#ifndef ONLINE_JUDGE
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif // ONLINE_JUDGE*/
    ll t,test=1;
    //cin>>test;
    F(t,1,test+1) {
        //cout<<"Case #"<<t<<": ";
        solve();
        nl
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()

void solve(){
  int n;cin>>n;
  vector<int> v(n);
  REP(i,n)cin>>v[i];
  vector<int> ans;
  REP(i,n*n){
    if(i&1){
      for(int j=1;j<n-1;j+=2){//j:odd
        if(v[j]>v[j+1]){
          ans.push_back(j+1);
          swap(v[j],v[j+1]);
          j=n;
        }
      }
    }
    else{
      for(int j=0;j<n-1;j+=2){
        if(v[j]>v[j+1]){
          ans.push_back(j+1);
          swap(v[j],v[j+1]);
          j=n;
        }
      }
    }
    if(ans.size()<=i){
      bool ok=1;
      for(int j=0;j<n;j++)ok&=v[j]==j+1;
      if(ok)break;
      if((i&1)^((n-2)&1)){
        ans.push_back(n-2);
        swap(v[n-3],v[n-2]);
      }
      else{
        ans.push_back(n-1);
        swap(v[n-2],v[n-1]);
      }
    }
  }
  cout<<ans.size()<<endl;for(int p:ans)cout<<p<<" ";cout<<endl;
}

signed main(){
  int t;cin>>t;
  while(t--)solve();
}
