Problem: Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony.

<image>

A sequence of positive integers bi 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 bi which minimizes the following expression:

<image>

You are given sequence ai, 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 a1, a2, ..., an (1 ≤ ai ≤ 30).

Output

Output the key — sequence bi 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 

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {

	public static void main(String[] args) {
		TaskD mSol = new TaskD();
		mSol.solve();
		mSol.flush();
		mSol.close();
	}

}

class TaskD {

	public FasterScanner mFScanner;
	public PrintWriter mOut;
	public int mArray[];
	public int mAns[];
	public int mDp[][];
	public int mFact[];
	public static final int[] mPrimes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19,
			23, 29, 31, 37, 41, 43, 47, 53, 59 };
	public int mDpMask[][];
	public static final int MAX = 999999;

	public TaskD() {
		mFScanner = new FasterScanner();
		mOut = new PrintWriter(System.out);
	}

	public void solve() {
		int N;
		int i;

		N = mFScanner.nextInt();
		mArray = new int[N];
		mAns = new int[N];
		mDp = new int[101][1 << 17];
		mDpMask = new int[101][1 << 17];
		mFact = new int[60];

		for (i = 0; i < N; i++) {
			mArray[i] = mFScanner.nextInt();
		}

		populateFact();

		solveDP(N);

	}

	public void populateFact() {
		int i;
		int k;
		int num;

		mFact[1] = 0;
		for (i = 2; i < 60; i++) {
			num = i;
			for (k = 0; k < mPrimes.length; k++) {
				if (num % mPrimes[k] == 0) {
					mFact[i] |= (1 << k);
				}
				while (num % mPrimes[k] == 0) {
					num /= mPrimes[k];
				}

				if (num == 1)
					break;
			}
		}
	}

	public void solveDP(int N) {
		int i;
		int s;
		int k;
		int fact;
		int val;
		int min = MAX;
		int minIndex;

		for (i = 0; i <= N; i++) {
			if (i == 0)
				Arrays.fill(mDp[0], 0);
			else
				Arrays.fill(mDp[i], MAX);

		}

		for (i = 1; i <= N; i++) {

			for (s = 1; s < 60; s++) {
				fact = mFact[s];
				fact = ~fact;
				fact = fact & ((1 << 17) - 1);
				for (k = fact;; k = (k - 1) & fact) {
					val = mDp[i - 1][k] + Math.abs(mArray[i - 1] - s);

					if (val < mDp[i][k | mFact[s]]) {
						mDp[i][k | mFact[s]] = val;
						mDpMask[i][k | mFact[s]] = k;
					}

					if (k == 0)
						break;
				}
			}

		}

		minIndex = 0;
		for (i = 0; i < (1 << 17); i++) {
			if (mDp[N][i] < min) {
				min = mDp[N][i];
				minIndex = i;
			}
		}

		Arrays.fill(mAns, MAX);

		for (i = N; i > 0; i--) {
			fact = mDpMask[i][minIndex];
			// mOut.println(minIndex + ": " + Integer.toBinaryString(minIndex));
			// mOut.println(fact + ": " + Integer.toBinaryString(fact));
			k = (~fact) & minIndex;

			min = MAX;
			for (s = 1; s < 60; s++) {
				if (mFact[s] == k) {
					if (Math.abs(mArray[i - 1] - s) < min) {
						min = Math.abs(mArray[i - 1] - s);
						mAns[i - 1] = s;
					}

				}
			}

			minIndex = fact;
		}

		// mOut.println(min);

		for (i = 0; i < N; i++)
			mOut.print(mAns[i] + " ");

		mOut.println();
	}

	public void flush() {
		mOut.flush();
	}

	public void close() {
		mOut.close();
	}

}

class FasterScanner {
	private InputStream mIs;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;

	public FasterScanner() {
		this(System.in);
	}

	public FasterScanner(InputStream is) {
		mIs = is;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = mIs.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public String nextString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}

}