Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Little Pony and Harmony Chest

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPrincess 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.

Examples

Input

5

1 1 1 1 1

Output

1 1 1 1 1

Input

5

1 6 4 2 8

Output

1 5 3 1 8

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2017 12:13:30 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|