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 D259 {
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);

	short INF = 30000;
	
	boolean[] primeList;
	
	boolean isPrime(int n) {
		if (n < 0) return false;
		return primeList[n];
	}
	
	boolean[] getPrimeList(int n) {
		boolean[] res = new boolean[n+1];
		
		Arrays.fill(res, true);
		
		res[0] = res[1] = false;
		for (int i = 2; i < res.length; i++) {
			if (!res[i]) continue;
			for (int j = 2 * i; j < res.length; j += i) {
				res[j] = false;
			}
		}
		
		return res;
	}
	
	
	public void run() {
		int n = in.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) a[i] = in.nextInt();
		
		int[] fact = new int[61];
		primeList = getPrimeList(100);
		for (int i = 1; i < 61; i++) {
			int val = 0, shift = 0, div = i;
			for (int j = 2; j < 61; j++) {
				if (div % j == 0) {
					while (div % j == 0) {
						div /= j;
					}
					val |= (1 << shift);
				}
				if (primeList[j]) shift++;
			}
			fact[i] = val;
		}
		
		int[][] prev = new int[n+1][1<<17];
		short[][] dp = new short[n+1][1<<17];
		short[][] val = new short[n+1][1<<17];
		
		for (int i = 0; i <= n; i++) Arrays.fill(dp[i], INF);
		dp[0][0] = 0;
		
		for (int i = 0; i < n; i++) {
			for (int j = 1; j < 61; j++) {
				int bit = fact[j] ^ ((1 << 17) - 1);
				for (int s = bit; ; s = (s - 1) & bit) {
					if (dp[i][s] + Math.abs(a[i] - j) < dp[i+1][s | fact[j]]) {
						dp[i+1][s | fact[j]] = (short) (dp[i][s] + Math.abs(a[i] - j));
						val[i+1][s | fact[j]] = (short)j;
						prev[i+1][s | fact[j]] = s;
					}
					if (s == 0) break;
				}
			}
		}

		int[] res = new int[n];
		
		int min = Integer.MAX_VALUE, idx = 0;
		for (int i = 0; i < (1 << 17); i++) {
			if (dp[n][i] < min) {
				min = dp[n][i];
				idx = i;
			}
		}
		
		for (int i = n - 1; i >= 0; i--) {
			res[i] = val[i+1][idx];
			idx = prev[i+1][idx];
		}
		
		for (int i = 0; i < n; i++) {
			System.out.print(res[i] + " ");
		}
		System.out.println();
		out.close();
	}

	public static void main(String[] args) {
		new D259().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

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

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		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++];
		}

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

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

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

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

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