Насте подарили массив целых положительных чисел длины \(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\) наборов входных данных в первой строке выведите одно целое число \(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\).
Если существует несколько решений, выведите любое из них.
Примечание
Рассмотрим первый набор входных данных.
Изначально \(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]\) — хороший массив.
Во втором наборе входных данных исходный массив уже является хорошим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
9 6 3 11 15
3
7 5 13
|
2
1 5 11 9
2 5 7 6
0
|