This source is shared by jerry99

//jerry99
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int tmax=105;
const int smax=140000;
int n,a[tmax],f[tmax][smax],g[tmax][smax],top=(1<<17)-1;
int pr[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};//17个
int s[tmax],print[tmax];
void init()
{
    int i,j,tmp;
    for(i=1;i<60;i++)
    {
        tmp=0;
        for(j=0;j<17;j++)
            if(i%pr[j]==0) tmp+=1<<j;
        s[i]=tmp;
    }
    return;
}
void test()
{
    int i;
    for(i=1;i<60;i++)
        printf("%d:%d\n",i,s[i]);
    return;
}
int main()
{
    init();
    cin>>n;
    int i,j,k;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(f,-1,sizeof(f));
    f[0][0]=0;
    for(i=1;i<=n;i++)
        for(j=0;j<=top;j++)
            for(k=1;k<60;k++)
            {
                if((j&s[k])!=s[k]) continue;
                if(f[i-1][j-s[k]]==-1) continue;
                if(f[i][j]==-1)
                {
                    f[i][j]=f[i-1][j-s[k]]+abs(a[i]-k);
                    g[i][j]=k;
                }
                else if(f[i][j]>f[i-1][j-s[k]]+abs(a[i]-k))
                {
                    f[i][j]=f[i-1][j-s[k]]+abs(a[i]-k);
                    g[i][j]=k;
                }
            }
    int ans=100000,num=0;
    for(j=0;j<=top;j++)
        if(f[n][j]!=-1&&ans>f[n][j])
    {
        ans=f[n][j];
        num=j;
    }
    for(i=n;i>=1;i--)
    {
        print[i]=g[i][num];
        num=num-s[print[i]];
    }
    for(i=1;i<=n;i++)
        printf("%d ",print[i]);
    //test();
    return 0;
}