Problem: You are given an array a consisting of n elements. You may apply several operations (possibly zero) to it.

During each operation, you choose two indices i and j (1 ≤ i, j ≤ n; i ≠ j), increase a_j by a_i, and remove the i-th element from the array (so the indices of all elements to the right to it decrease by 1, and n also decreases by 1).

Your goal is to make the array a strictly ascending. That is, the condition a_1 < a_2 < ... < a_n should hold (where n is the resulting size of the array).

Calculate the minimum number of actions required to make the array strictly ascending.

Input

The first line contains one integer T (1 ≤ T ≤ 10000) — the number of test cases.

Each test case consists of two lines. The first line contains one integer n (1 ≤ n ≤ 15) — the number of elements in the initial array a.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6).

It is guaranteed that: 

  * the number of test cases having n ≥ 5 is not greater than 5000; 
  * the number of test cases having n ≥ 8 is not greater than 500; 
  * the number of test cases having n ≥ 10 is not greater than 100; 
  * the number of test cases having n ≥ 11 is not greater than 50; 
  * the number of test cases having n ≥ 12 is not greater than 25; 
  * the number of test cases having n ≥ 13 is not greater than 10; 
  * the number of test cases having n ≥ 14 is not greater than 3; 
  * the number of test cases having n ≥ 15 is not greater than 1. 

Output

For each test case, print the answer as follows:

In the first line, print k — the minimum number of operations you have to perform. Then print k lines, each containing two indices i and j for the corresponding operation. Note that the numeration of elements in the array changes after removing elements from it. If there are multiple optimal sequences of operations, print any one of them.

Example

Input


4
8
2 1 3 5 1 2 4 5
15
16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
2
3 3
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14


Output


3
6 8
1 6
4 1
7
1 15
1 13
1 11
1 9
1 7
1 5
1 3
1
2 1
0

Note

In the first test case, the sequence of operations changes a as follows:

[2, 1, 3, 5, 1, 2, 4, 5] → [2, 1, 3, 5, 1, 4, 7] → [1, 3, 5, 1, 6, 7] → [2, 3, 5, 6, 7].

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <typename int_t>
inline int_t lowbit(int_t x) {
  return x & -x;
}
inline int h_bit(unsigned long long x) {
  return int(sizeof(unsigned long long) * 8 - __builtin_clzll(x));
}
unsigned long long pow2(unsigned long long x) {
  return x == lowbit(x) ? x : 1ull << h_bit(x);
}
template <typename T>
int get_bit(T a, int i) {
  return a >> i & 1;
}
template <typename T>
T get_mid(T l, T r) {
  assert(l <= r);
  return l + (r - l >> 1);
}
using std::to_string;
std::string to_string(const std::string &s) { return '"' + s + '"'; }
std::string to_string(const char *s) { return to_string((std::string)s); }
std::string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
std::string to_string(const std::pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <size_t N>
std::string to_string(const std::bitset<N> &bs) {
  return bs.to_string();
}
template <typename A>
std::string to_string(const A &v) {
  bool first = true;
  std::string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_out(const Head &H, const Tail &...T) {
  std::cerr << " " << to_string(H);
  debug_out(T...);
}
struct fast_ios {
  fast_ios() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
  };
} fast_ios_;
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &vec) {
  for (auto &x : vec) stream >> x;
  return stream;
}
template <typename T, typename U>
std::istream &operator>>(std::istream &in, std::pair<T, U> &p) {
  in >> p.first >> p.second;
  return in;
}
void scan() {}
template <class T, class... Args>
void scan(T &a, Args &...rest) {
  std::cin >> a;
  scan(rest...);
}
template <typename T>
std::ostream &operator<<(std::ostream &stream, const std::vector<T> &vec) {
  bool first = true;
  for (const T &t : vec) {
    if (first)
      first = false;
    else
      std::cout << ' ';
    std::cout << t;
  }
  return stream;
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &p) {
  out << p.first << ' ' << p.second;
  return out;
}
template <typename T>
void print(const std::vector<std::vector<T>> &t) {
  for (const auto &row : t) {
    std::cout << row << '\n';
  }
}
template <typename T>
void print(const T &t) {
  std::cout << t << ' ';
}
template <typename T, typename... Args>
void print(const T &t, const Args &...rest) {
  print(t);
  print(rest...);
}
template <typename T>
void println(const T &t) {
  std::cout << t << '\n';
}
template <typename T, typename... Args>
void println(const T &t, const Args &...rest) {
  print(t);
  println(rest...);
}
template <typename A, typename B>
bool chkmin(A &a, const B &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <typename A, typename B>
bool chkmax(A &a, const B &b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}
using ll = long long;
using ull = unsigned long long;
using vl = std::vector<ll>;
using vb = std::vector<bool>;
using vi = std::vector<int>;
using pii = std::pair<int, int>;
using pli = std::pair<ll, int>;
using pll = std::pair<ll, ll>;
using vpii = std::vector<pii>;
template <typename T>
using vv = std::vector<std::vector<T>>;
template <typename T, typename U = std::less<T>>
using pq = std::priority_queue<T, std::vector<T>, U>;
template <typename T, typename U>
T ceil(T x, U y) {
  assert(y > 0);
  if (x > 0) x += y - 1;
  return x / y;
}
template <typename T, typename U>
T floor(T x, U y) {
  assert(y > 0);
  if (x < 0) x -= y - 1;
  return x / y;
}
using namespace std;
int dp[16][15][1 << 15];
pii pre[16][15][1 << 15];
int removed[16][15][1 << 15];
class FMakeItAscending {
 public:
  static void solve(int, int) {
    int T;
    scan(T);
    for (int _iter_213 = 0, _num_213 = T; _iter_213 < _num_213; ++_iter_213) {
      int n;
      scan(n);
      vi a(n);
      scan(a);
      const int tot = 1 << n, all = tot - 1;
      for (std::common_type<decltype(1), decltype(n)>::type i = 1; i <= n; ++i)
        for (std::common_type<decltype(0), decltype(n)>::type j = 0; j < n; ++j)
          for (std::common_type<decltype(0), decltype(tot)>::type s = 0;
               s < tot; ++s)
            dp[i][j][s] = 0;
      vi sum(tot);
      for (std::common_type<decltype(0), decltype(tot)>::type i = 0; i < tot;
           ++i) {
        for (std::common_type<decltype(0), decltype(n)>::type j = 0; j < n;
             ++j) {
          if (get_bit(i, j)) sum[i] += a[j];
        }
      }
      for (std::common_type<decltype(1), decltype(tot)>::type s = 1; s < tot;
           ++s) {
        int i = __builtin_ctz(s);
        dp[1][i][s] = sum[s];
        pre[1][i][s] = {0, -1};
        removed[1][i][s] = s ^ 1 << i;
      }
      for (std::common_type<decltype(1), decltype(n)>::type i = 1; i < n; ++i) {
        for (std::common_type<decltype(0), decltype(n - 1)>::type j = 0;
             j < n - 1; ++j) {
          for (std::common_type<decltype(1), decltype(1 << n)>::type s = 1;
               s < 1 << n; ++s) {
            if (dp[i][j][s] == 0) continue;
            for (int u = all xor s, t = u; t > 0 && h_bit(t) - 1 > j;
                 t = t - 1 & u) {
              if (sum[t] <= dp[i][j][s]) continue;
              for (std::common_type<decltype(j + 1), decltype(n)>::type k =
                       j + 1;
                   k < n; ++k) {
                if (get_bit(t, k)) {
                  auto &tar = dp[i + 1][k][s | t];
                  if (tar == 0 or tar > sum[t]) {
                    tar = sum[t];
                    pre[i + 1][k][s | t] = {s, j};
                    removed[i + 1][k][s | t] =
                        removed[i][j][s] | (t xor 1 << k);
                  }
                  break;
                }
              }
            }
          }
        }
      }
      for (std::common_type<decltype(1), decltype(n)>::type i = n; i >= 1;
           i--) {
        bool flag = false;
        for (std::common_type<decltype(0), decltype(n)>::type j = 0; j < n; ++j)
          if (dp[i][j][all]) {
            vv<pii> ans(i + 1);
            int s = all;
            vi index(n);
            for (std::common_type<decltype(1), decltype(i)>::type k = i; k >= 1;
                 k--) {
              42;
              auto [ps, pj] = pre[k][j][s];
              42;
              int t = s ^ ps;
              42;
              if (__builtin_popcountll((t)) > 1) {
                int c = 0;
                int rs = removed[k - 1][pj][ps];
                for (std::common_type<decltype(0), decltype(n)>::type x = 0;
                     x < n; ++x) {
                  if (!get_bit(rs, x)) index[x] = ++c;
                }
                for (std::common_type<decltype(j + 1), decltype(n - 1)>::type
                         l = n - 1;
                     l >= j + 1; l--) {
                  if (get_bit(t, l)) ans[k].emplace_back(index[l], index[j]);
                }
                for (std::common_type<decltype(0), decltype(j - 1)>::type l =
                         j - 1;
                     l >= 0; l--) {
                  if (get_bit(t, l)) ans[k].emplace_back(index[l], index[j]--);
                }
              }
              s = ps;
              j = pj;
            }
            println(n - i);
            for (std::common_type<decltype(1), decltype(i)>::type k = 1; k <= i;
                 ++k) {
              for (const auto &p : ans[k]) println(p);
            }
            flag = true;
            break;
          }
        if (flag) break;
      }
    }
  }
};
int main() {
  FMakeItAscending solver;
  solver.solve(0, 0);
  return 0;
}