#include <iostream>
#include <fstream>

#define NMAX 13
using namespace std;

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

int n;

int sol[NMAX];

bool column[NMAX];

bool main_diag[2 * NMAX - 1];
bool sec_diag[2 * NMAX - 1];

int no_solutions;

void n_queens_problem(int k)
{
    if (k == n)
    {
        if (!no_solutions++)
        {
            for (int i = 0; i < n; ++i)
                g << sol[i] + 1 << " ";
            g << "\n";
        }
        return;
    }

    for (int c = 0; c < n; c++)
    {
        if (!column[c] && !main_diag[NMAX + k - c] && !sec_diag[k + c])
        {
            sol[k] = c;
            column[c] = main_diag[NMAX + k - c] = sec_diag[k + c] = true;
            n_queens_problem(k + 1);
            column[c] = main_diag[NMAX + k - c] = sec_diag[k + c] = false;
        }
    }
}

int main()
{
    f >> n;
    n_queens_problem(0);
    g << no_solutions << "\n";
}