#include<fstream>
using namespace std;
int i,j,nr[14]={0,0,0,0,2,10,4,40,92,352,724,2680,14200,73712},st[15],lev,n,sol[15];
bool ok=1;

int abs(int x) { if (x<0) return(-x); else return(x); }

void back(int lev) {
     if (lev>n&&ok) {
                        ok=0;
                        for (int i=1; i<=n; ++i) sol[i]=st[i];
                        
                }
     else if (ok) for (int i=st[lev]+1; i<=n; ++i) {
            
            bool aux=1;
            for (int j=1; j<lev; ++j) 
             if ( st[j]==i || ( abs(st[j]-i)==lev-j) ) { aux=0; break; }
            if (aux) { st[lev]=i; back(lev+1); st[lev]=0; }
            
            }
            
}

int main(void) {
    ifstream fin("damesah.in");
    ofstream fout("damesah.out");
    fin>>n;
    
    back(1);
    
    for (i=1; i<=n; ++i) fout<<sol[i]<<" ";
    fout<<"\n"<<nr[n];
  return(0);
}