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.*;
import java.util.*;
import java.math.BigInteger.*;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;


// https://netbeans.org/kb/73/java/editor-codereference_ru.html#display
//<editor-fold defaultstate="collapsed" desc="Main">
public class Main {
    private void run() {
        Locale.setDefault(Locale.US);
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }
        
        if (oj) {
            sc = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            try {
                sc = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch (IOException e) {
                MLE();
            }
        }
        Solver s = new Solver();
        s.sc = sc;
        s.out = out;
        s.solve();
        err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
        out.flush();
    }
    
    private void show(int[] arr) {
        for (int v : arr) {
            err.print(" " + v);
        }
        err.println();
    }
    
    public static void MLE() {
        int[][] arr = new int[1024 * 1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024 * 1024];
        }
    }
    
    public static void main(String[] args) {
        new Main().run();
    }
    
    long timeBegin = System.currentTimeMillis();
    FastScanner sc;
    PrintWriter out;
    PrintStream err = System.err;
}
//</editor-fold>

//<editor-fold defaultstate="collapsed" desc="FastScanner">
class FastScanner {
    
    BufferedReader br;
    StringTokenizer st;
    
    FastScanner(InputStreamReader reader) {
        br = new BufferedReader(reader);
        st = new StringTokenizer("");
    }
    
    String next() {
        while (!st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException ex) {
                Main.MLE();
            }
        }
        return st.nextToken();
    }
    
    int nextInt() {
        return Integer.parseInt(next());
    }
    
    long nextLong() {
        return Long.parseLong(next());
    }
}
//</editor-fold>


class Solver {

    FastScanner sc;
    PrintWriter out;
    PrintStream err = System.err;

    final int buben = 60;
    final int NNN = 17;
    int n;
    int[] a, b, ansB;
    int ans = Integer.MAX_VALUE;
    int[][] gcd = new int[1000][1000];
    {
        for (int i = 0; i < gcd.length; i++) {
            for (int j = 0; j < gcd.length; j++) {
                gcd[i][j] = gcd(i,j);
            }
        }
    }
    
    int gcd (int a, int b) {
	return b!=0 ? gcd (b, a % b) : a;
    }
    
    void f( int pos, final int curAns ){
        if( pos == n ){
            //err.println(Arrays.toString(b) +":: " + curAns);
            if( ans > curAns ){
                ans = curAns;
                ansB = b.clone();
            }
        }
        else{
            //for( int val = pos==0? 1 : b[pos-1]; val <= buben; ++val ){
            for( int val = pos==0? 1 : b[pos-1]; val <= min(buben,a[pos]+35); ++val ){
                b[pos] = val;
                
                int posAns = curAns;
                for (int i = pos; i < n; i++) {
                    int bi = val + i - pos;
                    if( a[i] <= bi )
                        posAns += abs( bi - a[i]);
                    else break;
                }
                if( ans < posAns ) break;
                
                boolean OK = true;
                int[] gcd_val = gcd[val];
                for (int i = 0; i < pos; i++) {
                    if( gcd_val[b[i]] == 0 ) Main.MLE();
                    if( gcd_val[b[i]] != 1 ){
                        OK = false;
                        break;
                    }
                }
                if( OK ){
                    f( pos + 1, curAns + abs(a[pos]-b[pos]) );
                } 
            }
        }
    }
    
    class Item{
        int val, ind;
        Item( int _val, int _ind ){
            val = _val;
            ind = _ind;
        }
    }
    
    void solve(){
        n = sc.nextInt();
        a = new int[n];
        Item[] arr = new Item[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            //a[i] = 30;
            arr[i] = new Item(a[i],i);
        }
        sort( a );
        b = new int[n];
        
        
        if( NNN <= n ){
            fill( b, 1 );
            int curAns = 0;
            for( int i = 0; i < n-NNN; ++i ) curAns += abs(a[i]-1);
            f( n-NNN, curAns );
        }
        else
            f( 0, 0 );
        err.println(Arrays.toString(ansB));
        
        sort( arr, (a,b)-> a.val - b.val );
        
        int ind = 0;
        for ( Item it : arr ) {
            b[it.ind] = ansB[ind];
            ++ind;
        }
        
        for (int i = 0; i < n; i++) {
            out.print( " " + b[i] );
        }
        err.println( "ans: " + ans );
    }

  

}