B. Повелитель значений
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Торгуя на своей любимой бирже, трейдер Василий вдруг понял, что нашел в ней уязвимость. С помощью этой уязвимости он может менять некоторые значения служебных переменных в свою пользу. Чтобы навести суеты, он решил поменять все значения служебных переменных $$$a_1, a_2, \ldots, a_n$$$ на $$$-a_1, -a_2, \ldots, -a_n$$$. По непонятной причине, количество служебных переменных — всегда четное число.

Василий понимает, что каждым своим действием он будет привлекать все больше внимания службы безопасности, поэтому количество его действий не должно превышать $$$5\,000$$$, а также после каждой операции ни одна из переменных по модулю не должна превышать $$$10^{18}$$$. Василий может совершать два типа действий для двух выбранных переменных с индексами $$$i$$$ и $$$j$$$, где $$$i < j$$$:

  1. Выполнить присваивание $$$a_i = a_i + a_j$$$
  2. Выполнить присваивание $$$a_j = a_j - a_i$$$

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

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

Во входных данных находится несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 20$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка набора входных данных содержит одно целое четное число $$$n$$$ ($$$2 \le n \le 10^3$$$) — количество системных переменных.

Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — описание начального состояния системных переменных.

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

Для каждого набора входных данных выведите ответ в следующем формате:

Первая строка вывода должна содержать количество действий $$$k$$$, которое совершит стратегия. Обратите внимание, что вам не требуется минимизировать $$$k$$$. Должно выполняться неравенство $$$k \le 5\,000$$$.

Следующие $$$k$$$ строк должны содержать действия в формате «type i j», где «type» равен «1», если стратегии нужно выполнить присваивание первого типа, и «2» — если стратегии нужно выполнить присваивание второго типа. Обратите внимание, что должно выполняться $$$i < j$$$.

Можно показать, что ответ всегда существует.

Пример
Входные данные
2
4
1 1 1 1
4
4 3 1 2
Выходные данные
8
2 1 2
2 1 2
2 1 3
2 1 3
2 1 4
2 1 4
1 1 2
1 1 2
8
2 1 4
1 2 4
1 2 4
1 2 4
1 3 4
1 1 2
1 1 2
1 1 4
Примечание

В первом тестовом примере одной из возможных последовательностей операций может быть следующая:

  1. «2 1 2». Значения переменных после применения операции: [1, 0, 1, 1]
  2. «2 1 2». Значения переменных после применения операции: [1, -1, 1, 1]
  3. «2 1 3». Значения переменных после применения операции: [1, -1, 0, 1]
  4. «2 1 3». Значения переменных после применения операции: [1, -1, -1, 1]
  5. «2 1 4». Значения переменных после применения операции: [1, -1, -1, 0]
  6. «2 1 4». Значения переменных после применения операции: [1, -1, -1, -1]
  7. «1 1 2». Значения переменных после применения операции: [0, -1, -1, -1]
  8. «1 1 2». Значения переменных после применения операции: [-1, -1, -1, -1]

Во втором тестовом примере одной из возможных последовательностей операций может быть следующая:

  1. «2 1 4». Значения переменных после применения операции: [4, 3, 1, -2]
  2. «1 2 4». Значения переменных после применения операции: [4, 1, 1, -2]
  3. «1 2 4». Значения переменных после применения операции: [4, -1, 1, -2]
  4. «1 2 4». Значения переменных после применения операции: [4, -3, 1, -2]
  5. «1 3 4». Значения переменных после применения операции: [4, -3, -1, -2]
  6. «1 1 2». Значения переменных после применения операции: [1, -3, -1, -2]
  7. «1 1 2». Значения переменных после применения операции: [-2, -3, -1, -2]
  8. «1 1 4». Значения переменных после применения операции: [-4, -3, -1, -2]