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

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;

int t, n;

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--) {
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i]; a[i]--;
		}
		vector<int> ans;
		for (int i = 0; i < n; ++i) {
			int j = find(a.begin(), a.end(), i) - a.begin();
			if (i == j) continue;
			if (j % 2 == (int)ans.size() % 2) {
				if (j >= i + 2) {
					ans.push_back(j - 2);
					swap(a[j-2], a[j-1]);
				}
				else {
					ans.push_back(i - 1);
					ans.push_back(i);
					ans.push_back(i - 1);
					ans.push_back(i);
					ans.push_back(i - 1);
					swap(a[i], a[j]);
					continue;
				}
			}
			for (int k = j - 1; k >= i; --k) {
				ans.push_back(k);
				swap(a[k], a[k+1]);
			}
		}
		cout << ans.size() << '\n';
		for (int i = 0; i < (int)ans.size(); ++i) {
			cout << ans[i] + 1 << ' ';
		}
		cout << '\n';
	}
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define FOR(i,f,n) for(int i=f;i<n;i++)
#define FORI(i,f,n) for(int i=f;i>=n;i--)
#define sz(a) ((int)(a).size())
#define ff first
#define ss second
#define all(a) (a).begin(),(a).end()
#define alli(a) (a).rbegin(),(a).rend()
#define approx(a) fixed<<setprecision(a)
#define trav(a,x) for(auto& a : x)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,bool> pib;
typedef pair<ll,bool> plb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T> void ckmin(T &a, const T &b) { a = min(a, b); }
template <class T> void ckmax(T &a, const T &b) { a = max(a, b); }
 
template <class T> void read(vector<T> &v);
template <class F, class S> void read(pair<F, S> &p);
template <class T> void read(T &x) {cin>>x;}
template <class R, class... T> void read(R& r, T&... t){read(r); read(t...);};
template <class T> void read(vector<T> &v) {trav(x, v) read(x);}
template <class F, class S> void read(pair<F, S> &p) {read(p.ff, p.ss);}
 
template <class F, class S> void pr(const pair<F, S> &x);
template <class T> void pr(const T &x) {cout<<x;}
template <class R, class... T> void pr(const R& r, const T&... t) {pr(r); pr(t...);}
template <class F, class S> void pr(const pair<F, S> &x) {pr("{", x.ff, ", ", x.ss, "}");}
void ps() {pr("\n");}
template <class T> void ps(const T &x) {pr(x); ps();}
template <class T> void ps(vector<T> &v) {trav(x, v) pr(x, ' '); ps();}
template <class F, class S> void ps(const pair<F, S> &x) {pr(x.ff, ' ', x.ss); ps();}
template <class R, class... T> void ps(const R& r, const T &...t) {pr(r, ' '); ps(t...);}

const int MXN = 2e5+1;
vi adj[MXN], level[MXN], in(MXN), out(MXN);
int timer = 0;

void dfs(int v, int d){
    in[v] = ++timer;
    level[d].pb(in[v]);
    for(int u : adj[v]){    
        dfs(u, d+1);
    }
    out[v] = ++timer;
}

void solve(){
    int n; read(n);
    FOR(i,1,n){
        int x; read(x);
        adj[x].pb(i+1);
    }
    dfs(1, 0);
    int q; read(q);
    FOR(i,0,q){
        int u, d; read(u, d);
        int ans = lower_bound(all(level[d]), out[u]) - lower_bound(all(level[d]), in[u]);
        ps(ans);
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}