CF453B Little Pony and Harmony Chest

Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony. :::align{center}  ::: A sequence of positive integers $ b_{i} $ is harmony if and only if for every two elements of the sequence their greatest common divisor equals $1$. According to an ancient book, the key of the chest is a harmony sequence $ b_{i} $ which minimizes the following expression: $$ \sum_{i=1}^n|a_i-b_i| $$ You are given sequence $ a_{i} $, help Princess Twilight to find the key.

The first line contains an integer $ n $ ( $ 1\le n\le100 $ ) — the number of elements of the sequences $ a $ and $ b $. The next line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1\le a_{i}\le30 $ ).

Output the key — sequence $ b_{i} $ that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.