#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int isPossible(vector<vector<int>> mat, int x, int y, int n) {
    // verific daca o alta regina ataca pozitia x y
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // daca e regina, marchez pozitiile atacate cu -1
            if (mat[i][j] == 1) {
                // linia i
                for (int k = 0; k < n; k++) {
                    if (k != j) {
                        mat[i][k] = -1;
                    }
                }

                // coloana j
                for (int k = 0; k < n; k++) {
                    if (k != i) {
                        mat[k][j] = -1;
                    }
                }

                // diagonalele
                for (int k = 0; k < n; k++) {
                    if (i - k >= 0 && j - k >= 0) {
                        mat[i-k][j-k] = -1;
                    }
                    if (i + k < n && j + k < n) {
                        mat[i+k][j+k] = -1;
                    }
                    if (i - k >= 0 && j + k < n) {
                        mat[i-k][j+k] = -1;
                    }
                    if (i + k < n && j - k >= 0) {
                        mat[i+k][j-k] = -1;
                    }
                }
            }
        }
    }

    if (mat[x][y] == 0) {
        return 1;
    }
    return 0;
}

void solveDame(vector<vector<int>>& mat, int line, int n, int& nr_sol) {
    // ma opresc daca am pus n dame pe tabla, cate una pe linie
    if (line == n) {
        if (nr_sol == 0) {
            nr_sol++;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (mat[i][j] == 1) {
                        fout << (j + 1) << ' ';
                    }
                }
            }
        } else {
            nr_sol++;
        }
        return;
    }

    for (int j = 0; j < n; j++) {
        // incerc sa pun o regina pe tabla
        if (isPossible(mat, line, j, n)) {
            mat[line][j] = 1;
            solveDame(mat, line + 1, n, nr_sol);
            mat[line][j] = 0;
        }
    }
}

int main() {
    int n;
    fin >> n;

    vector<vector<int>> mat(n, vector<int>(n, 0));
    int nr_sol = 0;

    solveDame(mat, 0, n, nr_sol);

    fout << '\n' << nr_sol << '\n';

    return 0;
}