B. Настя и хороший массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Насте подарили массив целых положительных чисел длины $$$n$$$.

Она называет такой массив $$$a$$$ хорошим, что для любого $$$i$$$ ($$$2 \le i \le n$$$) выполняется $$$gcd(a_{i - 1}, a_{i}) = 1$$$, где $$$gcd(u, v)$$$ обозначает наибольший общий делитель (НОД) чисел $$$u$$$ и $$$v$$$.

Вы можете выполнять такую операцию: выбрать некоторые различные индексы $$$i, j$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$), а также два целых числа $$$x, y$$$ ($$$1 \le x, y \le 2 \cdot 10^9$$$). При этом должно выполняться $$$\min{(a_i, a_j)} = \min{(x, y)}$$$. Затем заменить $$$a_i$$$ на $$$x$$$, а $$$a_j$$$ на $$$y$$$.

Девочка просит вас за не более чем $$$n$$$ операций сделать массив хорошим.

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

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных.

В первой строке каждого набора задано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина массива Насти.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_{n}$$$ ($$$1 \le a_i \le 10^9$$$) — массив Насти.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого из $$$t$$$ наборов входных данных в первой строке выведите одно целое число $$$k$$$ ($$$0 \le k \le n$$$) — количество выполненных вами операций. Вам не нужно минимизировать это число.

В каждой из последующих $$$k$$$ строк выведите $$$4$$$ целых числа $$$i$$$, $$$j$$$, $$$x$$$, $$$y$$$ ($$$1 \le i \neq j \le n$$$, $$$1 \le x, y \le 2 \cdot 10^9$$$) такие, что $$$\min{(a_i, a_j)} = \min{(x, y)}$$$ — таким образом вы заменяете $$$a_i$$$ на $$$x$$$; $$$a_j$$$ на $$$y$$$.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
2
5
9 6 3 11 15
3
7 5 13
Выходные данные
2
1 5 11 9
2 5 7 6
0
Примечание

Рассмотрим первый набор входных данных.

Изначально $$$a = [9, 6, 3, 11, 15]$$$.

В первой операции заменяем $$$a_1$$$ на $$$11$$$; $$$a_5$$$ на $$$9$$$. Это возможно потому, что $$$\min{(a_1, a_5)} = \min{(11, 9)} = 9$$$.

После этой операции $$$a = [11, 6, 3, 11, 9]$$$.

Во второй операции заменяем $$$a_2$$$ на $$$7$$$; $$$a_5$$$ на $$$6$$$. Это возможно потому, что $$$\min{(a_2, a_5)} = \min{(7, 6)} = 6$$$.

После этой операции $$$a = [11, 7, 3, 11, 6]$$$ — хороший массив.

Во втором наборе входных данных исходный массив уже является хорошим.