暮光公主前往塞拉斯蒂娅和露娜的古老城堡研究和谐元素的宝箱。
正整数 bi 的序列是和谐的,当且仅当该序列的每两个元素的最大公约数等于 1。根据一本古书,宝箱的钥匙是和谐序列 bi ,它最小化了以下表达式:
$$\sum_{i=1}^{n}|a_i - b_i|$$
给你序列ai,帮助暮光公主找到钥匙。
输入
第一行包含一个整数 n (1 ≤ n ≤ 100) — 序列 a 和 b 的元素数量。下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 30)。
输出
输出最小化上述总和的密钥 — 序列 bi 。如果有多个最优序列,则可以输出其中任意一个。
示例
输入 #1
5 1 1 1 1 1
输出 #1
1 1 1 1 1
输入 #2
5 1 6 4 2 8
输出 #2
1 5 3 1 8