#include <iostream>
#include <fstream>
#include <unordered_map>

using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");

#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 30 + 5;

int N,nrSol;
bool a[NMax][NMax]; // tabla de sah

void backT(int,int);
bool checkDiag1(int,int); // verifica daca exista o dama pe diagonala
bool checkDiag2(int,int);
bool checkRow(int);
bool checkCol(int);
// checkDiag1(i,j); // verifica daca exista o dama pe prima diagonala unei dame de pe pozitia (i,j)
// checkDiag2(i,j); // verifica daca exista o dama pe a doua diagonala a unei dame de pe pozitia (i,j)
// checkRow(i); // verifica daca exista o dama pe randul i;
// checkCol(j); // verifica daca exista o dama pe coloana j;

int main() {
    in>>N;

    backT(1,1);
    out<<'\n'<<nrSol<<'\n';

    in.close();out.close();
    return 0;
}

void backT(int nr,int x) {
    if (nr == N + 1) {
        if (!nrSol) { // nu s-a afisat inca o solutie

            for (int i=1;i <= N;++i) {
                for (int j=1;j <= N;++j) {
                    if (a[i][j]) {
                        out<<j<<' ';
                        break;
                    }
                }
            }
        }

        ++nrSol;
        return;
    }

    // x - linia pe care se va pune noua dama
    for (int i=x;i <= N;++i) {
        for (int j=1;j <= N;++j) {
            if (checkDiag1(i,j) && checkDiag2(i,j) &&
                checkRow(i) && checkCol(j)) {

                a[i][j] = 1;
                backT(nr+1,i+1);
                a[i][j] = 0;
            }
        }
    }
}

bool checkDiag1(int x,int y) {
    int i,j;
    i = x; j = y;

    while (i && j) {
        if (a[i][j]) {
            return false;
        }
        --i; --j;
    }

    i = x; j = y;
    while (i <= N && j <= N) {
        if (a[i][j]) {
            return false;
        }

        ++i; ++j;
    }

    return true;
}

bool checkDiag2(int x,int y) {
    int i,j;
    i = x; j = y;

    while (i <= N && j) {
        if (a[i][j]) {
            return false;
        }
        ++i; --j;
    }

    i = x; j = y;
    while (i && j <= N) {
        if (a[i][j]) {
            return false;
        }

        --i; ++j;
    }

    return true;
}

bool checkRow(int x) {
    for (int j=1;j <= N;++j) {
        if (a[x][j]) {
            return false;
        }
    }

    return true;
}

bool checkCol(int y) {
    for (int i=1;i <= N;++i) {
        if (a[i][y]) {
            return false;
        }
    }

    return true;
}