F. Сделай возрастающим
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Вы можете применить несколько операций к этому массиву (возможно, ни одной).

Во время каждой операции вы выбираете два индекса $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$; $$$i \ne j$$$), увеличиваете $$$a_j$$$ на $$$a_i$$$, а затем удаляете $$$i$$$-й элемент из массива (при этом индексы всех элементов правее удаляемого уменьшаются на $$$1$$$, и размер массива $$$n$$$ также уменьшается на $$$1$$$).

Ваша цель — сделать массив $$$a$$$ строго возрастающим, то есть должно выполняться условие $$$a_1 < a_2 < \dots < a_n$$$ (где $$$n$$$ — итоговый размер массива).

Посчитайте минимальное количество операций, которое требуется, чтобы массив стал возрастающим.

Входные данные

В первой строке задано одно целое число $$$T$$$ ($$$1 \le T \le 10000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк. Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 15$$$) — количество элементов в исходном массиве $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Гарантируется, что:

  • количество наборов тестовых данных, в которых $$$n \ge 5$$$, не превосходит $$$5000$$$;
  • количество наборов тестовых данных, в которых $$$n \ge 8$$$, не превосходит $$$500$$$;
  • количество наборов тестовых данных, в которых $$$n \ge 10$$$, не превосходит $$$100$$$;
  • количество наборов тестовых данных, в которых $$$n \ge 11$$$, не превосходит $$$50$$$;
  • количество наборов тестовых данных, в которых $$$n \ge 12$$$, не превосходит $$$25$$$;
  • количество наборов тестовых данных, в которых $$$n \ge 13$$$, не превосходит $$$10$$$;
  • количество наборов тестовых данных, в которых $$$n \ge 14$$$, не превосходит $$$3$$$;
  • количество наборов тестовых данных, в которых $$$n \ge 15$$$, не превосходит $$$1$$$.
Выходные данные

На каждый набор тестовых данных выведите ответ следующим образом:

Сначала выведите $$$k$$$ — минимальное количество операций, которые вы должны сделать. Затем выведите $$$k$$$ строк, каждая из которых содержит два индекса $$$i$$$ и $$$j$$$ для соответствующей операции. Обратите внимание, что нумерация элементов меняется после удаления элемента из массива. Если существует несколько оптимальных последовательностей операций, выведите любую из них.

Пример
Входные данные
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
Выходные данные
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
Примечание

В первом наборе тестовых данных $$$a$$$ меняется следующим образом:

$$$[2, 1, 3, 5, 1, 2, 4, 5] \rightarrow [2, 1, 3, 5, 1, 4, 7] \rightarrow [1, 3, 5, 1, 6, 7] \rightarrow [2, 3, 5, 6, 7]$$$.