Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony. 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: You are given sequence a i , help Princess Twilight to find the key.

输入描述:

The first line contains an integer n (1 ≤ n ≤ 100) — the number of elements of the sequences a and b. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 30).

输出描述:

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