// http://www.infoarena.ro/problema/damesah
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int N,v[20],ok,nr_sol;
void bkt(int lin);
void afisare();
bool valid(int col,int lin);
int main()
{
    fin>>N;
    bkt(1);
    fout<<nr_sol;
    return 0;
}
void bkt(int lin) {
    if(lin==N+1) {
        if(ok==0) {
            afisare();
            ok=1;
        }
        nr_sol++;
    }
    else {
        for(int i=1;i<=N;i++) {
            if(valid(i,lin)) {
                v[lin]=i;
                bkt(lin+1);
                v[lin]=0;
            }
        }
    }
}
bool valid(int col,int lin) {
    int i;
    for(i=1;i<lin;i++) {
        if(v[i]==col) return false; //aceeasi coloana
    }
    if(col-1>0 && lin-1>0 && v[lin-1]==col-1) return false; //diagonala
    if(col+1<=N && lin-1>0 && v[lin-1]==col+1) return false;
    if(col-1>0 && lin+1<=N && v[lin+1]==col-1) return false;
    if(col+1<=N && lin+1<=N && v[lin+1]==col+1) return false;
    return true;
}
void afisare() {
    for(int i=1;i<=N;i++) fout<<v[i]<<" ";
    fout<<endl;
}