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:
/**
 * ******* Created  on 25/4/20 12:54 AM*******
 */

import java.io.*;
import java.util.*;

public class B453 implements Runnable {

    private static final int MAX = 60;
    private static final int MOD = (int) (1E9 + 7);
    private static final long Inf = (long) (1E14 + 10);
    private static final double eps = (double) (1E-9);

    /**
     *  Bitmasks number therory gcd sieve
     * @throws IOException
     */
    int n;
    int[] a;
    int[] fact = new int[MAX+1];
    private void solve() throws IOException {
        n = reader.nextInt();
        a = new int[n];
        for(int i=0;i<n;i++)
            a[i] = reader.nextInt();
        List<Integer> primes = getPrimes();

        for(int i=1;i<=MAX;i++){
            for(int j=0;j<primes.size() ;j++){
                if(i%primes.get(j)==0)
                    fact[i] |=(1<<j);
            }
        }
        mem = new int[n][1<<17];
        for(int i=0;i<n;i++)
            Arrays.fill(mem[i],-1);
        dp(0,0);
        path(0,0);
    }

    private int path(int i, int mask) {
        if(i == n)
            return 0;
        int ans = dp(i, mask);
        if(ans == Math.abs(a[i]-1) +dp(i+1, mask) ){
            writer.print("1 ");
            return path(i+1, mask);
        }
        for(int j=2;j<=60;j++){
            if((mask & fact[j]) ==0)
                if(ans == Math.abs(a[i]-j) + dp(i+1, mask | fact[j])){
                    writer.print(j +" ");
                    return path(i+1, mask | fact[j]);
                }
        }
        return 0;
    }

    int[][] mem ;
    int ans ;
    private int dp(int i, int mask) {
        if(i == n)
            return 0;
        if(mem[i][mask]!=-1)
            return mem[i][mask];
        ans =Math.abs(a[i]-1) + dp(i+1, mask);
        for(int j=2;j<=60;j++){
            if((mask & fact[j] )==0 )
                ans = Math.min(ans, Math.abs(a[i]-j)+dp(i+1,mask | fact[j]));
        }
        mem[i][mask] = ans;
        return ans;
    }

    private List<Integer> getPrimes() {
        List<Integer> primes = new ArrayList<>();
        for(int i=2;i<=MAX;i++){
            boolean flag =true;
            for(int j=2;j<i;j++)
                if(i%j==0)
                    flag =false;
            if(flag)primes.add(i);
        }

        return primes;
    }

    public static void main(String[] args) throws IOException {
        try (Input reader = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            new B453().run();
        }
    }

    StandardInput reader;
    PrintWriter writer;

    @Override
    public void run() {
        try {
            reader = new StandardInput();
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    interface Input extends Closeable {
        String next() throws IOException;

        String nextLine() throws IOException;

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

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

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

        default int[] readIntArray() throws IOException {
            return readIntArray(nextInt());
        }

        default int[] readIntArray(int size) throws IOException {
            int[] array = new int[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        default long[] readLongArray(int size) throws IOException {
            long[] array = new long[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextLong();
            }
            return array;
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }

        @Override
        public String nextLine() throws IOException {
            return reader.readLine();
        }
    }

}