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.util.Arrays;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Writer;
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;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        int CONSIDER = 58;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int[] primes = IntegerUtils.generatePrimes(59);
            int[] toMask = new int[CONSIDER + 1];
            for (int i = 1; i < toMask.length; i++) toMask[i] = getMask(i, primes);
            int n = in.readInt();
            int[] a = IOUtils.readIntArray(in, n);
            int[][] dp = new int[n + 1][1 << primes.length];
            ArrayUtils.fill(dp, 1000 * 1000 * 1000);
            dp[0][0] = 0;
            int[][] prevMask = new int[n + 1][1 << primes.length];
            int[][] prevTaken = new int[n + 1][1 << primes.length];
            for (int index = 0; index < n; index++) {
                for (int mask = 0; mask < (1 << primes.length); mask++) {
                    for (int consider = 1; consider <= CONSIDER; consider++) { // maybe 53 is upper bound?
                        int delta = Math.abs(consider - a[index]);
                        int mHere = toMask[consider];
                        if ((mHere & mask) == 0) {
                            int nMask = (mHere | mask);
                            int cost = dp[index][mask] + delta;
                            if (dp[index + 1][nMask] > cost) {
                                dp[index + 1][nMask] = cost;
                                prevMask[index + 1][nMask] = mask; // index is always index - 1
                                prevTaken[index + 1][nMask] = consider;
                            }
                        }
                    }
                }
            }
            int bestMask = -1, bestCost = 1000 * 1000 * 1000;
            for (int mask = 0; mask < (1 << primes.length); mask++) {
                if (dp[n][mask] < bestCost) {
                    bestCost = dp[n][mask];
                    bestMask = mask;
                }
            }
            int index = n;
            int mask = bestMask;
            ArrayList<Integer> res = new ArrayList<>();
            for (int i = n; i > 0; i--) {
                res.add(prevTaken[i][mask]);
                mask = prevMask[i][mask];
            }
            Collections.reverse(res);
            for (int val : res) out.print(val + " ");
            out.printLine();
        }

        private int getMask(int val, int[] primes) {
            int mask = 0;
            while (val > 1) {
                for (int i = 0; i < primes.length; i++) {
                    if (val % primes[i] == 0) {
                        mask |= (1 << i);
                        val /= primes[i];
                        break;
                    }
                }
            }
            return mask;
        }
    }
    static abstract class IntAbstractStream implements IntStream {
        public String toString() {
            StringBuilder builder = new StringBuilder();
            boolean first = true;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                if (first) {
                    first = false;
                } else {
                    builder.append(' ');
                }
                builder.append(it.value());
            }
            return builder.toString();
        }

        public boolean equals(Object o) {
            if (!(o instanceof IntStream)) {
                return false;
            }
            IntStream c = (IntStream) o;
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                if (it.value() != jt.value()) {
                    return false;
                }
                it.advance();
                jt.advance();
            }
            return !it.isValid() && !jt.isValid();
        }

        public int hashCode() {
            int result = 0;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                result *= 31;
                result += it.value();
            }
            return result;
        }
    }
    static interface IntStream extends Iterable<Integer>, Comparable<IntStream> {
        public IntIterator intIterator();
        default public Iterator<Integer> iterator() {
            return new Iterator<Integer>() {
                private IntIterator it = intIterator();

                public boolean hasNext() {
                    return it.isValid();
                }

                public Integer next() {
                    int result = it.value();
                    it.advance();
                    return result;
                }
            };
        }
        default public int compareTo(IntStream c) {
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                int i = it.value();
                int j = jt.value();
                if (i < j) {
                    return -1;
                } else if (i > j) {
                    return 1;
                }
                it.advance();
                jt.advance();
            }
            if (it.isValid()) {
                return 1;
            }
            if (jt.isValid()) {
                return -1;
            }
            return 0;
        }
    }
    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine() {
            writer.println();
        }

        public void close() {
            writer.close();
        }
    }
    static interface IntIterator {
        public int value() throws NoSuchElementException;
        public boolean advance();
        public boolean isValid();
    }
    static class IntegerUtils {
        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];
            if (upTo < 2) {
                return isPrime;
            }
            Arrays.fill(isPrime, -1);
            isPrime[0] &= -4;
            for (int i = 2; i * i < upTo; i++) {
                if ((isPrime[i >> 5] >>> (i & 31) & 1) == 1) {
                    for (int j = i * i; j < upTo; j += i) {
                        isPrime[j >> 5] &= -1 - (1 << (j & 31));
                    }
                }
            }
            return isPrime;
        }
    }
    static class IntArrayList extends IntAbstractStream implements IntList {
        private int size;
        private int[] data;

        public IntArrayList() {
            this(3);
        }

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

        public IntArrayList(IntCollection c) {
            this(c.size());
            addAll(c);
        }

        public IntArrayList(IntStream c) {
            this();
            if (c instanceof IntCollection) {
                ensureCapacity(((IntCollection) c).size());
            }
            addAll(c);
        }

        public IntArrayList(IntArrayList c) {
            size = c.size();
            data = c.data.clone();
        }

        public IntArrayList(int[] arr) {
            size = arr.length;
            data = arr.clone();
        }

        public int size() {
            return size;
        }

        public int get(int at) {
            if (at >= size) {
                throw new IndexOutOfBoundsException("at = " + at + ", size = " + size);
            }
            return data[at];
        }

        private void ensureCapacity(int capacity) {
            if (data.length >= capacity) {
                return;
            }
            capacity = Math.max(2 * data.length, capacity);
            data = Arrays.copyOf(data, capacity);
        }

        public void addAt(int index, int value) {
            ensureCapacity(size + 1);
            if (index > size || index < 0) {
                throw new IndexOutOfBoundsException("at = " + index + ", size = " + size);
            }
            if (index != size) {
                System.arraycopy(data, index, data, index + 1, size - index);
            }
            data[index] = value;
            size++;
        }

        public void removeAt(int index) {
            if (index >= size || index < 0) {
                throw new IndexOutOfBoundsException("at = " + index + ", size = " + size);
            }
            if (index != size - 1) {
                System.arraycopy(data, index + 1, data, index, size - index - 1);
            }
            size--;
        }
    }
    static interface IntList extends IntReversableCollection {
        public abstract int get(int index);
        public abstract void addAt(int index, int value);
        public abstract void removeAt(int index);
        default public IntIterator intIterator() {
            return new IntIterator() {
                private int at;
                private boolean removed;

                public int value() {
                    if (removed) {
                        throw new IllegalStateException();
                    }
                    return get(at);
                }

                public boolean advance() {
                    at++;
                    removed = false;
                    return isValid();
                }

                public boolean isValid() {
                    return !removed && at < size();
                }

                public void remove() {
                    removeAt(at);
                    at--;
                    removed = true;
                }
            };
        }
        default public void add(int value) {
            addAt(size(), value);
        }
    }
    static interface IntReversableCollection extends IntCollection {
    }
    static interface IntCollection extends IntStream {
        public int size();
        default public void add(int value) {
            throw new UnsupportedOperationException();
        }
        default public int[] toArray() {
            int size = size();
            int[] array = new int[size];
            int i = 0;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                array[i++] = it.value();
            }
            return array;
        }
        default public IntCollection addAll(IntStream values) {
            for (IntIterator it = values.intIterator(); it.isValid(); it.advance()) {
                add(it.value());
            }
            return this;
        }
    }
    static class IOUtils {
        public static int[] readIntArray(InputReader in, int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = in.readInt();
            }
            return array;
        }
    }
    static class ArrayUtils {
        public static void fill(int[][] array, int value) {
            for (int[] row : array) {
                Arrays.fill(row, value);
            }
        }
    }
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        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 readInt() {
            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) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

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

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}