Принцесса Twilight пришла к Celestia в замок, где раньше жила Luna, чтобы исследовать ларец элементов гармонии.
Последовательность положительных целых чисел bi называется гармонической тогда и только тогда, когда наибольший общий делитель любых двух ее элементов равен 1. Согласно древней книге, ключ от ларца — это гармоническая последовательность bi, минимизирующая значение выражения:
Вам дана последовательность ai. Помогите принцессе Twilight найти ключ от ларца.
Выходные данные
Выведите ключ — последовательность bi, которая минимизирует сумму, описанную выше. Если существует несколько правильных последовательностей, выведите любую.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 1 1 1
|
1 1 1 1 1
|
|
2
|
5
1 6 4 2 8
|
1 5 3 1 8
|