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.

Input

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 $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($1 ≤ *a*_{*i*} ≤ 30$).

Output

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