#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int Sol[20], N, nrsol;

void PrintSol()
{
    for(int i=1; i<=N; i++)
        fout << Sol[i] << ' ';
    fout << '\n';
}

bool valid(int c, int k)
{
    int j;
    for(j=1; j<k; j++)
        if(abs(c - Sol[j]) == abs(k-j) || c == Sol[j]) return 0;
    return 1;
}

void PutQueen(int k)
{
    if(k == N+1)
    {
        if(nrsol == 0) PrintSol();
        nrsol++;
    }
    else
    {
        int c;
        for(c=1; c<=N; c++)
            if(valid(c, k))
            {
                Sol[k] = c;
                PutQueen(k+1);
            }
    }
}

int main()
{
    fin >> N;
    PutQueen(1);
    fout << nrsol << '\n'; fin.close(); fout.close();
    return 0;
}