#include<fstream>
#define maxn 16
#define maxd 32
using namespace std;
ifstream fi("damesah.in");
ofstream fo("damesah.out");

int i,n,v[maxn],sol=0;
short int col[maxn];
short int diag_p[maxd],diag_s[maxd];

void tipar(int n){
     int i;
     for(i=1;i<=n;i++) fo<<v[i]<<" ";
     fo<<"\n";
}

void back(int k){
     int i;
     if(n+1==k){
                sol++;
                if(sol==1) tipar(n);
               }
     else for(i=1;i<=n;i++)
            {
             v[k]=i;
             if(!col[i] && !diag_p[k+v[k]] && !diag_s[v[k]-k+n])
                 {
                  col[i]=1; diag_p[k+v[k]]=1; diag_s[v[k]-k+n]=1;
                  back(k+1);
                  col[i]=0; diag_p[k+v[k]]=0; diag_s[v[k]-k+n]=0; 
                 }
            }
}

int main(){
    fi>>n; 
    for(i=0;i<=n+2;i++){
                        col[i]=0;
                        diag_p[i]=0;
                        diag_s[i]=0;
                       }
    
    back(1);
    fo<<sol;
    
    fi.close();
    fo.close();
    return 0;
}