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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.BufferedInputStream;
import java.util.concurrent.Callable;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		BufferedInputStream in = new BufferedInputStream(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskB {
		public void solve(int testNumber, BufferedInputStream _in, PrintWriter out) {

			InputReader in = new InputReader(_in);
			long startTime = System.currentTimeMillis();
			int nt = 1;
			Task t = new Task(1);
			t.readInput(in);
			t.call();
			t.writeOutput(out);
			in.close();
			System.err.println("Time: " + (System.currentTimeMillis() - startTime) + " miliseconds");
		}

	}

	static final class MathPreconditions {
		static long checkNonNegative(String role, long x) {
			if (x < 0) {
				throw new IllegalArgumentException(role + " (" + x + ") must be >= 0");
			}
			return x;
		}

		private MathPreconditions() {
		}

	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

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

		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 static boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public void close() {

		}

	}

	static class Task implements Callable<Task> {
		static ArrayList<Integer> primes = new ArrayList<>();
		static int nPrime;
		static int[] mask = new int[61];
		static int INF = (int) 1e9;
		static final int MAXB = 60;
		int n;
		int[] a;
		ArrayList<Integer> ret = new ArrayList<>();
		int testNumber;

		static {
			for (int i = 2; i <= MAXB; ++i)
				if (IntMath.isPrime(i)) primes.add(i);
			nPrime = primes.size();

			for (int i = 2; i <= MAXB; ++i) {
				for (int j = 0; j < nPrime; ++j)
					if (i % primes.get(j) == 0) {
						mask[i] |= (1 << j);
					}

//			System.err.println(i + " " + mask[i]);
			}
		}

		public void readInput(InputReader in) {
	/* read input here */
			n = in.nextInt();
			a = new int[n];
			for (int i = 0; i < n; ++i) a[i] = in.nextInt();
		}

		public Task call() {
	/* process main algorithm here */
			int[][] dp = new int[n][1 << nPrime];
			int[][] prev = new int[n][1 << nPrime];

			Arrays.fill(dp[0], INF);
			for (int i = 1; i <= MAXB; ++i) {
				if (dp[0][mask[i]] > Math.abs(i - a[0])) {
					dp[0][mask[i]] = Math.abs(i - a[0]);
					prev[0][mask[i]] = i;
				}
			}

//		for (int i = 1; i < n; ++i) {
//			Arrays.fill(dp[i], INF);
//			for (int j = 0; j < (1 << nPrime); ++j)
//				if (dp[i - 1][j] != INF) {
//					for (int k = 1; k <= MAXB; ++k)
//						if ((j & mask[k]) == 0) {
//					//	System.err.println(k + " " + j + " " + dp[i - 1][j]);
//							if (dp[i][j | mask[k]] > dp[i - 1][j] + Math.abs(k - a[i])) {
//								dp[i][j | mask[k]] = dp[i - 1][j] + Math.abs(k - a[i]);
//								prev[i][j | mask[k]] = k;
//							}
//						}
//				}
//		}

			for (int i = 1; i < n; ++i) {
				Arrays.fill(dp[i], INF);
				for (int k = 1; k <= MAXB; ++k) {
					int set = mask[k];
					set = (~set) & ((1 << nPrime) - 1);
					for (int subset = (set - 1) & set; ; subset = ((subset - 1) & set)) {
						if (dp[i][subset | mask[k]] > dp[i - 1][subset] + Math.abs(k - a[i])) {
							dp[i][subset | mask[k]] = dp[i - 1][subset] + Math.abs(k - a[i]);
							prev[i][subset | mask[k]] = k;
						}
						if (subset == 0) break;
					}
				}
			}

			int best = INF;
			int save = 0;

			for (int i = 0; i < (1 << nPrime); ++i) {
				if (best > dp[n - 1][i]) {
					best = dp[n - 1][i];
					save = i;
				}
			}

			for (int i = n - 1; i >= 0; --i) {
				ret.add(prev[i][save]);
				save -= mask[prev[i][save]];
			}
			Collections.reverse(ret);
			;


			System.err.println("Test case: " + testNumber + " done!");
			return this;
		}

		public void writeOutput(PrintWriter out) {
			for (int i = 0; i < n; ++i) out.print(ret.get(i) + " ");
		}

		Task(int testNumber) {
			this.testNumber = testNumber;
		}

	}

	static final class Longs {
		private Longs() {
		}

		public static int compare(long a, long b) {
			return (a < b) ? -1 : ((a > b) ? 1 : 0);
		}

	}

	static final class IntMath {
		public static boolean isPrime(int n) {
			return LongMath.isPrime(n);
		}

		private IntMath() {
		}

	}

	static final class UnsignedLongs {
		private UnsignedLongs() {
		}

		private static long flip(long a) {
			return a ^ Long.MIN_VALUE;
		}

		public static int compare(long a, long b) {
			return Longs.compare(flip(a), flip(b));
		}

		public static long remainder(long dividend, long divisor) {
			if (divisor < 0) { // i.e., divisor >= 2^63:
				if (compare(dividend, divisor) < 0) {
					return dividend; // dividend < divisor
				} else {
					return dividend - divisor; // dividend >= divisor
				}
			}

			// Optimization - use signed modulus if dividend < 2^63
			if (dividend >= 0) {
				return dividend % divisor;
			}

    /*
	 * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
     * guaranteed to be either exact or one less than the correct value. This follows from the fact
     * that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not
     * quite trivial.
     */
			long quotient = ((dividend >>> 1) / divisor) << 1;
			long rem = dividend - quotient * divisor;
			return rem - (compare(rem, divisor) >= 0 ? divisor : 0);
		}

	}

	static final class LongMath {
		static final long FLOOR_SQRT_MAX_LONG = 3037000499L;
		private static final int SIEVE_30 = ~((1 << 1) | (1 << 7) | (1 << 11) | (1 << 13)
				| (1 << 17) | (1 << 19) | (1 << 23) | (1 << 29));
		private static final long[][] millerRabinBaseSets = {
				{291830, 126401071349994536L},
				{885594168, 725270293939359937L, 3569819667048198375L},
				{273919523040L, 15, 7363882082L, 992620450144556L},
				{47636622961200L, 2, 2570940, 211991001, 3749873356L},
				{
						7999252175582850L,
						2,
						4130806001517L,
						149795463772692060L,
						186635894390467037L,
						3967304179347715805L
				},
				{
						585226005592931976L,
						2,
						123635709730000L,
						9233062284813009L,
						43835965440333360L,
						761179012939631437L,
						1263739024124850375L
				},
				{Long.MAX_VALUE, 2, 325, 9375, 28178, 450775, 9780504, 1795265022}
		};

		public static boolean isPrime(long n) {
			if (n < 2) {
				MathPreconditions.checkNonNegative("n", n);
				return false;
			}
			if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13) {
				return true;
			}

			if ((SIEVE_30 & (1 << (n % 30))) != 0) {
				return false;
			}
			if (n % 7 == 0 || n % 11 == 0 || n % 13 == 0) {
				return false;
			}
			if (n < 17 * 17) {
				return true;
			}

			for (long[] baseSet : millerRabinBaseSets) {
				if (n <= baseSet[0]) {
					for (int i = 1; i < baseSet.length; i++) {
						if (!LongMath.MillerRabinTester.test(baseSet[i], n)) {
							return false;
						}
					}
					return true;
				}
			}
			throw new AssertionError();
		}

		private LongMath() {
		}

		private enum MillerRabinTester {
			/**
			 * Works for inputs ≤ FLOOR_SQRT_MAX_LONG.
			 */
			SMALL {
				long mulMod(long a, long b, long m) {
        /*
         * NOTE(lowasser, 2015-Feb-12): Benchmarks suggest that changing this to
         * UnsignedLongs.remainder and increasing the threshold to 2^32 doesn't pay for itself, and
         * adding another enum constant hurts performance further -- I suspect because bimorphic
         * implementation is a sweet spot for the JVM.
         */
					return (a * b) % m;
				}


				long squareMod(long a, long m) {
					return (a * a) % m;
				}
			},
			/**
			 * Works for all nonnegative signed longs.
			 */
			LARGE {
				/** Returns (a + b) mod m. Precondition: {@code 0 <= a}, {@code b < m < 2^63}. */
				private long plusMod(long a, long b, long m) {
					return (a >= m - b) ? (a + b - m) : (a + b);
				}

				/**
				 * Returns (a * 2^32) mod m. a may be any unsigned long.
				 */
				private long times2ToThe32Mod(long a, long m) {
					int remainingPowersOf2 = 32;
					do {
						int shift = Math.min(remainingPowersOf2, Long.numberOfLeadingZeros(a));
						// shift is either the number of powers of 2 left to multiply a by, or the biggest shift
						// possible while keeping a in an unsigned long.
						a = UnsignedLongs.remainder(a << shift, m);
						remainingPowersOf2 -= shift;
					} while (remainingPowersOf2 > 0);
					return a;
				}


				long mulMod(long a, long b, long m) {
					long aHi = a >>> 32; // < 2^31
					long bHi = b >>> 32; // < 2^31
					long aLo = a & 0xFFFFFFFFL; // < 2^32
					long bLo = b & 0xFFFFFFFFL; // < 2^32

        /*
         * a * b == aHi * bHi * 2^64 + (aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo.
         *       == (aHi * bHi * 2^32 + aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo
         *
         * We carry out this computation in modular arithmetic. Since times2ToThe32Mod accepts any
         * unsigned long, we don't have to do a mod on every operation, only when intermediate
         * results can exceed 2^63.
         */
					long result = times2ToThe32Mod(aHi * bHi /* < 2^62 */, m); // < m < 2^63
					result += aHi * bLo; // aHi * bLo < 2^63, result < 2^64
					if (result < 0) {
						result = UnsignedLongs.remainder(result, m);
					}
					// result < 2^63 again
					result += aLo * bHi; // aLo * bHi < 2^63, result < 2^64
					result = times2ToThe32Mod(result, m); // result < m < 2^63
					return plusMod(
							result,
							UnsignedLongs.remainder(aLo * bLo /* < 2^64 */, m),
							m);
				}


				long squareMod(long a, long m) {
					long aHi = a >>> 32; // < 2^31
					long aLo = a & 0xFFFFFFFFL; // < 2^32

        /*
         * a^2 == aHi^2 * 2^64 + aHi * aLo * 2^33 + aLo^2
         *     == (aHi^2 * 2^32 + aHi * aLo * 2) * 2^32 + aLo^2
         * We carry out this computation in modular arithmetic.  Since times2ToThe32Mod accepts any
         * unsigned long, we don't have to do a mod on every operation, only when intermediate
         * results can exceed 2^63.
         */
					long result = times2ToThe32Mod(aHi * aHi /* < 2^62 */, m); // < m < 2^63
					long hiLo = aHi * aLo * 2;
					if (hiLo < 0) {
						hiLo = UnsignedLongs.remainder(hiLo, m);
					}
					// hiLo < 2^63
					result += hiLo; // result < 2^64
					result = times2ToThe32Mod(result, m); // result < m < 2^63
					return plusMod(
							result,
							UnsignedLongs.remainder(aLo * aLo /* < 2^64 */, m),
							m);
				}
			},;

			static boolean test(long base, long n) {
				// Since base will be considered % n, it's okay if base > FLOOR_SQRT_MAX_LONG,
				// so long as n <= FLOOR_SQRT_MAX_LONG.
				return ((n <= FLOOR_SQRT_MAX_LONG) ? SMALL : LARGE).testWitness(base, n);
			}

			abstract long mulMod(long a, long b, long m);

			abstract long squareMod(long a, long m);

			private long powMod(long a, long p, long m) {
				long res = 1;
				for (; p != 0; p >>= 1) {
					if ((p & 1) != 0) {
						res = mulMod(res, a, m);
					}
					a = squareMod(a, m);
				}
				return res;
			}

			private boolean testWitness(long base, long n) {
				int r = Long.numberOfTrailingZeros(n - 1);
				long d = (n - 1) >> r;
				base %= n;
				if (base == 0) {
					return true;
				}
				// Calculate a := base^d mod n.
				long a = powMod(base, d, n);
				// n passes this test if
				//    base^d = 1 (mod n)
				// or base^(2^j * d) = -1 (mod n) for some 0 <= j < r.
				if (a == 1) {
					return true;
				}
				int j = 0;
				while (a != n - 1) {
					if (++j == r) {
						return false;
					}
					a = squareMod(a, n);
				}
				return true;
			}

		}

	}
}