#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <cmath>

#define DIM 13
using namespace std;

//ifstream f("in.in");
//ofstream g("out.out");

ifstream f("damesah.in");
ofstream g("damesah.out");


int v[DIM+5],u[DIM+5][DIM+5],n,sol = 0;

void backtrack(int pas){

    if(pas == n+1){

        sol++;

        if(sol == 1){

            /*for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    cout<<u[i][j]<<" ";
                }
                cout<<'\n';
            }*/

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

        return;
    }


    for(int i=1;i<=n;i++){
        if(u[i][pas]){
            continue;
        }

        v[pas] = i;
        for(int j=1;pas+j<=n;j++){
            if(i+j <= n)
                u[i+j][pas+j]++;
            u[i][pas+j]++;
            if(i-j > 0)
                u[i-j][pas+j]++;
        }
        backtrack(pas+1);
        for(int j=1;pas+j<=n;j++){
            if(i+j <= n)
                u[i+j][pas+j]--;
            u[i][pas+j]--;
            if(i-j > 0)
                u[i-j][pas+j]--;
        }
    }
}

int main()
{

    f>>n;
    backtrack(1);

    g<<sol;

    return 0;
}