#include <chrono>
#include <iostream>
#include <fstream>

class stopwatch
{
    std::chrono::high_resolution_clock::time_point start;

public:
    stopwatch()
        : start(std::chrono::high_resolution_clock::now())
    {
    }

    ~stopwatch()
    {
        auto duration = std::chrono::high_resolution_clock::now() - start;
        std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << " ms" << std::endl;
    }
}; 

#define NMAX 13
using namespace std;

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

// number of queens
int n;

// column sol[i] of queen on line i
int sol[NMAX + 1];

// column locations
bool column[NMAX + 1];

// main diagonal locations
bool main_diag[2 * NMAX + 1];

// secondary diagonal locations
bool sec_diag[2 * NMAX + 1];

// number of solutions
int no_solutions;

#define main_diag (main_diag + NMAX)
#define sec_diag (sec_diag + NMAX)

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

void n_queens_problem(int k)
{
    if (k == n + 1)
    {
        if (no_solutions == 0)
        {
            print_sol();
        }
        no_solutions++;
        return;
    }

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

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