///**HIGH**

#include <fstream>

using namespace std;

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

void backtrack(int line, int n);

int n, queens[14], sorin;

bool column[14], main_diagonal[28], secondary_diagonal[28];

int main()
{
    in>>n;
    backtrack(1, n);
    out<<'\n'<<sorin;
    return 0;
}

void backtrack(int line, int n)
{
    if (line==n+1)
    {
        if (sorin==0)
            for (register int i=1; i<=n; ++i)
                out<<queens[i]<<" ";
        ++sorin;
    }
    else
        for (register int col=1; col<=n; ++col)
            if (column[col]==false && main_diagonal[col-line+n-1]==false && secondary_diagonal[col+line]==false)
            {
                queens[line]=col;
                column[col]=main_diagonal[col-line+n-1]=secondary_diagonal[col+line]=true;
                backtrack(line+1, n);
                column[col]=main_diagonal[col-line+n-1]=secondary_diagonal[col+line]=false;
            }
}