#include <fstream>
#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;

// first solution
bool first_sol = true;

//#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";
}

bool valid(int line) {
    int col = sol[line];
    //return !(column[col] || main_diag[line - col] || sec_diag[n + 1 - line - col]);
    return !(column[col] || main_diag[line - col + n] || sec_diag[line + col]);
}

void n_queens_problem() {
    int k = 1, c;
    sol[k] = 0;
    while (k > 0) {
        if (sol[k] < n) {
            sol[k]++;
            if (valid(k)) {
                c = sol[k];
                //column[c] = main_diag[k - c] = sec_diag[n + 1 - k - c] = true;
                column[c] = main_diag[k - c + n] = sec_diag[k + c] = true;
                if (k == n) {
                    if (first_sol) {
                        print_sol();
                        first_sol = false;
                    }
                    no_solutions++;
                    //column[c] = main_diag[k - c] = sec_diag[n + 1 - k - c] = false;
                    column[c] = main_diag[k - c + n] = sec_diag[k + c] = false;
                }
                else {
                    k++;
                    sol[k] = 0;
                }
            }
        }
        else {
            c = sol[k - 1];
            //column[c] = main_diag[k - 1 - c] = sec_diag[n + 1 - (k - 1) - c] = false;
            column[c] = main_diag[k-1 - c + n] = sec_diag[k-1 + c] = false;
            k--;
        }
    }
}

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