#include <iostream>
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pb push_back
using namespace std;
using ll = long long;
const ll mod = 1e9+7;

ll fac[1000001];

void pre(){
    fac[0]=fac[1]=1;
    for(int i=2;i<=1000001;i++)
{

    fac[i]=(fac[i-1]*1LL*i)%mod;
}
}

ll binpower(ll a,ll n){
    ll res=1;
    while(n){

    if(n%2)
        res = (res*1LL*a)%mod;

        n/=2;
        a=(a*1LL*a)%mod;

    }
    return res;

}

ll nCrmod(ll n,ll r){


ll res= fac[n];
res = (res*1LL*binpower(fac[r],mod-2))%mod;
res= (res*1LL*binpower(fac[n-r],mod-2))%mod;
return res;

}

long long ncr(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}
ll modexp(ll a,ll b,ll m){
    if(b==0)return 1;
    if(b%2==0){
        ll y =  modexp(a,b/2,m);
        return (y*y)%m;
    }
    else{
        return ((a%m)*modexp(a,b-1,m))%m;
    }
}

ll modinv(ll a,ll m){
return modexp(a,m-2,m);
//works only for prime m.
//else calculate phi(m)-1.
}

void SieveOfEratosthenes(ll n)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (ll p=2; p*p<=n; p++)
    {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true)
        {
            // Update all multiples of p greater than or
            // equal to the square of it
            // numbers which are multiple of p and are
            // less than p^2 are already been marked.
            for (ll i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }

    // Print all prime numbers
    for (ll p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";
}

vector<int> Centroid(vector<int>g[],int n) {

        vector<int> centroid;
        vector<int> sz(n+1);
        function<void (int, int)> dfs = [&](int u, int prev) {
                sz[u] = 1;
                bool is_centroid = true;
                for (auto v : g[u]) if (v != prev) {
                        dfs(v, u);
                        sz[u] += sz[v];
                        if (sz[v] > n / 2) is_centroid = false;
                }
                if (n - sz[u] > n / 2) is_centroid = false;
                if (is_centroid) centroid.push_back(u);
        };
        dfs(1, 0);
        return centroid;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll ans=0;
    ll k =sqrt(n);
    set<ll>s;
    for(int i=2;i<=k;i++){
            ll p =i;
        for(int j=2;j<40;j++){
            p*=i;
            if(p>n)break;
            else s.insert(p);
        }
    }

cout<<n-s.size()<<endl;


    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define FOR(i, m, n) for (ll i(m); i < n; i++)
#define DWN(i, m, n) for (ll i(m); i >= n; i--)
#define REP(i, n) FOR(i, 0, n)
#define DW(i, n) DWN(i, n, 0)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define D(n) DW(i, n)
#define DD(n) DW(j, n)
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using gr = vector<vll>;
using wgr = vector<vpll>;
void add_edge(gr&g,ll x, ll y){ g[x].pb(y);g[y].pb(x); }
void add_edge(wgr&g,ll x, ll y, ll z){ g[x].eb(y,z);g[y].eb(x,z); }
template<typename T,typename U>
ostream& operator<<(ostream& os, const pair<T,U>& p) { 
    cerr << ' ' <<  p.x << ',' << p.y; return os; }
template <typename T> 
ostream& operator<<(ostream& os, const vector<T>& v) { 
    for(auto x: v) os << ' ' <<  x; return os; }
template <typename T> 
ostream& operator<<(ostream& os, const set<T>& v) { 
    for(auto x: v) os << ' ' <<  x; return os; }
template<typename T,typename U>
ostream& operator<<(ostream& os, const map<T,U>& v) { 
    for(auto x: v) os << ' ' <<  x; return os; }
struct d_ {
    template<typename T> d_& operator,(const T& x) {
        cerr << ' ' <<  x; return *this;}
} d_t;
#define dbg(args ...) { d_t,"|",__LINE__,"|",":",args,"\n"; }
#define deb(X ...) dbg(#X, "=", X);
#define EPS (1e-10)
#define INF (1LL<<61)
#define YES(x) cout << (x ? "YES" : "NO") << endl;
#define CL(A,I) (memset(A,I,sizeof(A)))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll X = 6;
struct S {
    vll v;
    bool z;
    vll ret;
    ll hsh() {
        ll ret = 0;
        for(auto i: v) { ret = X*ret + i; }
        ret = 2*ret + z;
        return ret;
    }
};

vll solve(ll n, vll v) {
    ll x=0;
    vll ret;
    bool z = 1;
    while(x<n-X) {
        while(x<n && v[x]==x) x++;
        if(x==n) break;
        ll p; F(n) if(v[i]==x) p=i;
        if((p&1)==z) {
            while(p!=x) {
                swap(v[p-1],v[p]);
                ret.pb(p-1);
                z = !z;
                p--;
            }
        } else {
            F(X-1) {
                if(((n-i-1)&1)==z && v[n-i-1]!=x && v[n-i-2]!=x) {
                    swap(v[n-i-1],v[n-i-2]);
                    ret.pb(n-i-2);
                    z = !z;
                    break;
                }
            }
        }
    }
    if(x!=n) {
        x = max(0ll, n-X);
        queue<S> q;
        vll w; FOR(i,x,n) w.pb(v[i]-x);
        q.push({w,z});
        set<ll> vis;
        ll m = w.size();
        while(q.size()) {
            auto cur = q.front(); q.pop();
            if(vis.count(cur.hsh())) continue;
            vis.insert(cur.hsh());
            bool ok = 1;
            F(m) ok &= cur.v[i]==i;
            if(ok) {
                for(auto i: cur.ret) ret.pb(i+x);
                break;
            }
            FOR(i,1,m) if(((i+x)&1)==cur.z) {
                S ss = cur;
                ss.z = !ss.z;
                ss.ret.pb(i-1);
                swap(ss.v[i-1], ss.v[i]);
                q.push(ss);
            }
        }
    }
    return ret;
}

void SOLVE() {
    ll n; cin >> n;
    vll v(n);
    F(n) {
        cin >> v[i];
        v[i]--;
    }
    auto ret = solve(n,v);
    cout << ret.size() << endl;
    for(auto i: ret) cout << i+1 << ' ';
    cout << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    ll _T; cin >> _T;
    REP(_,_T) SOLVE();
    return 0;
}
