#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
constexpr long long INF = 200000000000000001LL;
constexpr int INF32 = 2100000001;
size_t seed42 = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 rng(seed42);
std::uniform_int_distribution<int> unidistrib;
int randint() { return unidistrib(rng); }
using namespace std;
unsigned long long modulo = 1000000007;
int modulo32 = 1000000007;
unsigned long long poww(unsigned long long x, unsigned long long n) {
  if (n == 0) return 1;
  unsigned long long answ = poww(x, n / 2);
  answ = (answ * answ) % modulo;
  if (n % 2) answ = (answ * x) % modulo;
  return answ;
}
pair<int, int> operator+(const pair<int, int>& lhs, pair<int, int>& rhs) {
  return {lhs.first + rhs.first, lhs.second + rhs.second};
}
template <class T>
ostream& operator<<(ostream& lhs, pair<T, T>& rhs) {
  return (lhs << rhs.first << ":" << rhs.second);
}
int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(0);
  int t, n, k, m;
  cin >> t;
  while (t--) {
    cin >> n;
    vector<int> a(n);
    vector<int> a0, a1;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      if (i % 2)
        a1.push_back(a[i]);
      else
        a0.push_back(a[i]);
    }
    auto a_sorted = a;
    sort(a_sorted.begin(), a_sorted.end());
    sort(a0.begin(), a0.end());
    sort(a1.begin(), a1.end());
    bool good = true;
    for (int i = 0; i < n; ++i) {
      int tmp = i % 2 ? a1[i / 2] : a0[i / 2];
      if (a_sorted[i] != tmp) {
        good = false;
        break;
      }
    }
    if (!good) {
      cout << "-1\n";
      continue;
    }
    reverse(a0.begin(), a0.end());
    reverse(a1.begin(), a1.end());
    vector<int> answ;
    for (int i = 0; i < n / 2; ++i) {
      auto it = find(a.begin(), a.end(), a0[i]);
      if (it != a.begin()) {
        answ.push_back((it - a.begin()) + 1);
        reverse(a.begin(), it + 1);
      }
      it = find(a.begin(), a.end(), a1[i]);
      if (it != a.begin() + 1) {
        answ.push_back(it - a.begin());
        reverse(a.begin(), it);
      }
    }
    int minn = a_sorted[0];
    for (int i = 0; i < n / 2; ++i) {
      auto it = find(a.begin(), a.end(), minn);
      if (it != a.begin()) {
        answ.push_back((it - a.begin()) + 1);
        reverse(a.begin(), it + 1);
      }
      it = find(a.begin(), a.end(), a0[i]);
      answ.push_back((it - a.begin()) + 1);
      reverse(a.begin(), it + 1);
      answ.push_back(n - 2 * i);
      reverse(a.begin(), a.end() - 2 * i);
    }
    cout << answ.size() << "\n";
    for (auto el : answ) {
      cout << el << " ";
    };
    cout << "\n";
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

You have a permutation: an array a = [a_1, a_2, …, a_n] of distinct integers from 1 to n. The length of the permutation n is odd.

You need to sort the permutation in increasing order.

In one step, you can choose any prefix of the permutation with an odd length and reverse it. Formally, if a = [a_1, a_2, …, a_n], you can choose any odd integer p between 1 and n, inclusive, and set a to [a_p, a_{p-1}, …, a_1, a_{p+1}, a_{p+2}, …, a_n].

Find a way to sort a using no more than 5n/2 reversals of the above kind, or determine that such a way doesn't exist. The number of reversals doesn't have to be minimized.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 100). Description of the test cases follows.

The first line of each test case contains a single integer n (3 ≤ n ≤ 2021; n is odd) — the length of the permutation.

The second line contains n distinct integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — the permutation itself. 

It is guaranteed that the sum of n over all test cases does not exceed 2021.

Output

For each test case, if it's impossible to sort the given permutation in at most 5n/2 reversals, print a single integer -1.

Otherwise, print an integer m (0 ≤ m ≤ 5n/2), denoting the number of reversals in your sequence of steps, followed by m integers p_i (1 ≤ p_i ≤ n; p_i is odd), denoting the lengths of the prefixes of a to be reversed, in chronological order.

Note that m doesn't have to be minimized. If there are multiple answers, print any.

Example

Input


3
3
1 2 3
5
3 4 5 2 1
3
2 1 3


Output


4
3 3 3 3
2
3 5
-1

Note

In the first test case, the permutation is already sorted. Any even number of reversals of the length 3 prefix doesn't change that fact.

In the second test case, after reversing the prefix of length 3 the permutation will change to [5, 4, 3, 2, 1], and then after reversing the prefix of length 5 the permutation will change to [1, 2, 3, 4, 5].

In the third test case, it's impossible to sort the permutation.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
constexpr long long INF = 200000000000000001LL;
constexpr int INF32 = 2100000001;
size_t seed42 = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 rng(seed42);
std::uniform_int_distribution<int> unidistrib;
int randint() { return unidistrib(rng); }
using namespace std;
unsigned long long modulo = 1000000007;
int modulo32 = 1000000007;
unsigned long long poww(unsigned long long x, unsigned long long n) {
  if (n == 0) return 1;
  unsigned long long answ = poww(x, n / 2);
  answ = (answ * answ) % modulo;
  if (n % 2) answ = (answ * x) % modulo;
  return answ;
}
pair<int, int> operator+(const pair<int, int>& lhs, pair<int, int>& rhs) {
  return {lhs.first + rhs.first, lhs.second + rhs.second};
}
template <class T>
ostream& operator<<(ostream& lhs, pair<T, T>& rhs) {
  return (lhs << rhs.first << ":" << rhs.second);
}
int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(0);
  int t, n, k, m;
  cin >> t;
  while (t--) {
    cin >> n;
    vector<int> a(n);
    vector<int> a0, a1;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      if (i % 2)
        a1.push_back(a[i]);
      else
        a0.push_back(a[i]);
    }
    auto a_sorted = a;
    sort(a_sorted.begin(), a_sorted.end());
    sort(a0.begin(), a0.end());
    sort(a1.begin(), a1.end());
    bool good = true;
    for (int i = 0; i < n; ++i) {
      int tmp = i % 2 ? a1[i / 2] : a0[i / 2];
      if (a_sorted[i] != tmp) {
        good = false;
        break;
      }
    }
    if (!good) {
      cout << "-1\n";
      continue;
    }
    reverse(a0.begin(), a0.end());
    reverse(a1.begin(), a1.end());
    vector<int> answ;
    for (int i = 0; i < n / 2; ++i) {
      auto it = find(a.begin(), a.end(), a0[i]);
      if (it != a.begin()) {
        answ.push_back((it - a.begin()) + 1);
        reverse(a.begin(), it + 1);
      }
      it = find(a.begin(), a.end(), a1[i]);
      if (it != a.begin() + 1) {
        answ.push_back(it - a.begin());
        reverse(a.begin(), it);
      }
    }
    int minn = a_sorted[0];
    for (int i = 0; i < n / 2; ++i) {
      auto it = find(a.begin(), a.end(), minn);
      if (it != a.begin()) {
        answ.push_back((it - a.begin()) + 1);
        reverse(a.begin(), it + 1);
      }
      it = find(a.begin(), a.end(), a0[i]);
      answ.push_back((it - a.begin()) + 1);
      reverse(a.begin(), it + 1);
      answ.push_back(n - 2 * i);
      reverse(a.begin(), a.end() - 2 * i);
    }
    cout << answ.size() << "\n";
    for (auto el : answ) {
      cout << el << " ";
    };
    cout << "\n";
  }
  return 0;
}

```