Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only 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-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/08/2020 16:15:32 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|