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

Вам задан массив из n элементов. Вам нужно превратить его во взаимнопростый массив за наименьшее количество действий.

За одно действие вы можете вставить любое положительное целое число, не превосходящее величины 109, в любое место массива.

Массив называется взаимнопростым, если любая пара соседних чисел взаимнопроста.

В теории чисел два числа a и b называются взаимнопростыми, если единственным положительным делителем обоих чисел является число 1.

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

В первой строке находится целое число n (1 ≤ n ≤ 1000) — количество элементов в массиве.

Во второй строке находятся n целых чисел ai (1 ≤ ai ≤ 109) — элементы массива a.

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

В первой строке выведите целое число k — наименьшее количество элементов, которые нужно добавить в массив a, чтобы он стал взаимнопростым.

Во второй строке выведите n + k целых чисел aj — элементы массива a после добавления k элементов. Обратите внимание, что этот массив должен быть взаимнопростым, то есть все пары соседних элементов должны быть взаимнопросты. Также новый массив должен быть получен из исходного массива a добавлением ровно k элементов.

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

Пример
Входные данные
3
2 7 28
Выходные данные
1
2 7 9 28