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.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class D259 {
	InputStream is;
	PrintWriter out;
	/**
	 * Go to Sublime, copy & pase the input Use Ctrl+A, Ctrl+Shift+L, Ctrl+Enter
	 * to create this string
	 */
	String INPUT = "5\n1 6 4 2 8";
	String INPUT4 = "2 2";
	String INPUT5 = "100000 100000";
	static int O1 = 0;
	static int O2 = 0;
	static int O3 = 0;
	static int[][] dp;
	static int[] fac;
	static int[] arr = new int[0];
	static int MAX = 58;
	public static int f(int used, int i) {
//		debug("f called:" + used + " " + i);
		O1++;
		if(i == arr.length) {
			return 0;
		}
		if(dp[used][i] != -1) {
			return dp[used][i];
		}
		int ans = (int) 1e9;
		O2++;
		for (int x = 1; x <= MAX; x++) {
			O3++;
			int f = fac[x];
			if((used & f) > 0) {
				continue;
			}
			ans = Math.min(ans, Math.abs(arr[i] - x) + f(used | f, i+1));
		}
		return dp[used][i] = ans;
	}
	
	void solve() {
		int n = ni();
		arr = na(n);
		// len = 16
		int[] primes = generatePrimes(58);
		int plen = primes.length;
		debug(primes);
		fac = new int[60];
		
		Arrays.fill(fac, 0);
		int maxMask = 1 << plen;
		dp = new int[maxMask][n];

		for(int i = 0 ; i < dp.length; i ++) {
			Arrays.fill(dp[i], -1);
		}
		
		for(int i = 1 ; i < 60; i ++ ) {
			for(int j = 0 ; j < plen; j++) {
				if(i % primes[j] == 0) {
					fac[i] |= 1 << j;
				}
			}
		}
		debug(fac);
		
		int used = 0;
		f(0,0);
		int[] rs = new int[n];
		
		for(int i = 0 ; i < n; ++i) {
			for(int j = 0; j < 58; j++) {
				int f = fac[j];
				if((used & f) > 0) {
					continue;
				}
				int old_cost = f(used, i);
				int new_cost = Math.abs(j - arr[i]) + f(used|f, i+1);
				if(old_cost == new_cost) {
					rs[i] = j;
					used |= f;
					break;
				}
			}
		}
		
		for(int i = 0 ; i < n; i ++) {
			System.out.printf("%d%c",  rs[i], i==n-1?'\n': ' ');
		}
		debug(O1);
		debug(O2);
		debug(O3);
	}

	public static int[] generatePrimes(int upTo) {
		int[] isPrime = generateBitPrimalityTable(upTo);
		IntList primes = new IntArrayList();
		for (int i = 0; i < upTo; i++) {
			if ((isPrime[i >> 5] >>> (i & 31) & 1) == 1)
				primes.add(i);
		}
		return primes.toArray();
	}

	public static int[] generateBitPrimalityTable(int upTo) {
		int[] isPrime = new int[(upTo + 31) >> 5];
		// debug("(upTo + 31) >> 5:" + ((upTo + 31) >> 5));
		// debug("isPrime.length:" + isPrime.length);
		if (upTo < 2)
			return isPrime;
		Arrays.fill(isPrime, -1);
		isPrime[0] &= -4;

		for (int i = 2; i * i < upTo; i++) {
			// debug("==============Start at i:" + i + "==============");
			// debug("isPrime[i >> 5]:" + isPrime[i >> 5]);
			// de(isPrime[i >> 5]);
			// debug("isPrime[i >> 5] >>> (i & 31):" + (isPrime[i >> 5] >>> (i &
			// 31)));
			// de(isPrime[i >> 5] >>> (i & 31));
			// debug("(isPrime[i >> 5] >>> (i & 31) & 1):"+ (isPrime[i >> 5] >>>
			// (i & 31) & 1));

			if ((isPrime[i >> 5] >>> (i & 31) & 1) == 1) {
				for (int j = i * i; j < upTo; j += i) {
					// debug("----------- " + j + " -------------");
					// debug("(1 << (j & 31)):" +(1 << (j & 31)));
					// de((1 << (j & 31)));
					// debug("-1 - (1 << (j & 31)):" + (-1 - (1 << (j & 31))));
					// de(-1 - (1 << (j & 31)));
					 isPrime[j >> 5] &= -1 - (1 << (j & 31));
				}
			}
		}
		return isPrime;
	}

	/**
	 * Built using CHelper plug-in Actual solution is at the top
	 */
	static final int INF = (int) 1e9;

	private static boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private static void debug(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}

	private static void de(int i) {
		if (!oj)
			System.out.println("Bin:" + Integer.toBinaryString(i));
	}

	static int[][] packD(int n, int[] from, int[] to) {
		int[][] result = new int[n][];
		int[] goOutCount = new int[n];
		for (int f : from)
			goOutCount[f]++;
		for (int i = 0; i < n; i++)
			result[i] = new int[goOutCount[i]];
		for (int i = 0; i < from.length; i++) {
			--goOutCount[from[i]];
			result[from[i]][goOutCount[from[i]]] = to[i];
		}
		return result;
	}

	void run() throws Exception {
		is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);

		long s = System.currentTimeMillis();
		solve();
		out.flush();
		debug(System.currentTimeMillis() - s + "ms");
	}

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

	private byte[] inbuf = new byte[1024];
	private int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	/**
	 * Next Double.
	 */
	private double nd() {
		return Double.parseDouble(ns());
	}

	/**
	 * Next Char.
	 */
	private char nc() {
		return (char) skip();
	}

	/**
	 * Next String.
	 */
	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b !=
			// ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	/**
	 * Next Char array.
	 */
	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	/**
	 * Next Matrix.
	 */
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	/**
	 * Next Array.
	 */
	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	/**
	 * Next Integer.
	 */
	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	/**
	 * Next Long.
	 */
	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
}

abstract class IntCollection {
	public abstract IntIterator iterator();

	public abstract int size();

	public abstract void add(int value);

	public int[] toArray() {
		int size = size();
		int[] array = new int[size];
		int i = 0;
		for (IntIterator iterator = iterator(); iterator.isValid(); iterator
				.advance())
			array[i++] = iterator.value();
		return array;
	}

	public void addAll(IntCollection values) {
		for (IntIterator it = values.iterator(); it.isValid(); it.advance()) {
			add(it.value());
		}
	}

}

class IntArrayList extends IntList {
	private int[] array;
	private int size;

	public IntArrayList() {
		this(10);
	}

	public IntArrayList(int capacity) {
		array = new int[capacity];
	}

	public IntArrayList(IntList list) {
		this(list.size());
		addAll(list);
	}

	public int get(int index) {
		if (index >= size)
			throw new IndexOutOfBoundsException();
		return array[index];
	}

	public int size() {
		return size;
	}

	public void add(int value) {
		ensureCapacity(size + 1);
		array[size++] = value;
	}

	public void ensureCapacity(int newCapacity) {
		if (newCapacity > array.length) {
			int[] newArray = new int[Math.max(newCapacity, array.length << 1)];
			System.arraycopy(array, 0, newArray, 0, size);
			array = newArray;
		}
	}

	public int[] toArray() {
		int[] array = new int[size];
		System.arraycopy(this.array, 0, array, 0, size);
		return array;
	}

}

abstract class IntList extends IntCollection implements Comparable<IntList> {

	public abstract int get(int index);

	public IntIterator iterator() {
		return new IntIterator() {
			private int size = size();
			private int index = 0;

			public int value() throws NoSuchElementException {
				if (!isValid())
					throw new NoSuchElementException();
				return get(index);
			}

			public void advance() throws NoSuchElementException {
				if (!isValid())
					throw new NoSuchElementException();
				index++;
			}

			public boolean isValid() {
				return index < size;
			}
		};
	}

	public int hashCode() {
		int hashCode = 1;
		for (IntIterator i = iterator(); i.isValid(); i.advance())
			hashCode = 31 * hashCode + i.value();
		return hashCode;
	}

	public boolean equals(Object obj) {
		if (!(obj instanceof IntList))
			return false;
		IntList list = (IntList) obj;
		if (list.size() != size())
			return false;
		IntIterator i = iterator();
		IntIterator j = list.iterator();
		while (i.isValid()) {
			if (i.value() != j.value())
				return false;
			i.advance();
			j.advance();
		}
		return true;
	}

	public int compareTo(IntList o) {
		IntIterator i = iterator();
		IntIterator j = o.iterator();
		while (true) {
			if (i.isValid()) {
				if (j.isValid()) {
					if (i.value() != j.value()) {
						if (i.value() < j.value())
							return -1;
						else
							return 1;
					}
				} else
					return 1;
			} else {
				if (j.isValid())
					return -1;
				else
					return 0;
			}
			i.advance();
			j.advance();
		}
	}

}

interface IntIterator {
	public int value() throws NoSuchElementException;

	/*
	 * @throws NoSuchElementException only if iterator already invalid
	 */
	public void advance() throws NoSuchElementException;

	public boolean isValid();
}