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

Вам дан массив целых чисел $$$a_1, a_2, \dots, a_n$$$. Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • Выбрать любой элемент $$$a_i$$$ из массива и заменить его значение на любое целое число от $$$0$$$ до $$$a_i$$$ (включительно). Более формально, если $$$a_i < 0$$$, заменить $$$a_i$$$ на любое целое число из $$$[a_i, 0]$$$, иначе заменить $$$a_i$$$ на любое целое число из $$$[0, a_i]$$$.

Пусть $$$r$$$ — минимально возможное произведение всех $$$a_i$$$ после выполнения операции любое число раз.

Найдите минимальное количество операций, необходимое для того, чтобы произведение стало равно $$$r$$$. Также выведите одну такую кратчайшую последовательность операций. Если существует несколько ответов, можете вывести любой из них.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 100$$$) — длину массива.

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

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

Для каждого набора входных данных:

  • Первая строка должна содержать минимальное количество операций $$$k$$$ ($$$0 \leq k \leq n$$$).
  • $$$j$$$-я из следующих $$$k$$$ строк должна содержать два целых числа $$$i$$$ и $$$x$$$, которые описывают $$$j$$$-ю операцию. Эта операция заключается в замене $$$a_i$$$ на $$$x$$$.
Пример
Входные данные
4
1
155
4
2 8 -1 3
4
-1 0 -2 -5
4
-15 -75 -25 -30
Выходные данные
1
1 0
0
0
1
3 0
Примечание

В первом примере мы можем заменить значение первого элемента на $$$0$$$, и произведение станет $$$0$$$, что является минимально возможным произведением.

Во втором примере изначально произведение целых чисел равно $$$2 \cdot 8 \cdot (-1) \cdot 3 = -48$$$, что является минимально возможным произведением, поэтому в этом случае ничего делать не нужно.