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

void queens(int nq, int &sCount, std::vector<int> &sol, bool &first, std::ostream &out) {

    if (sol.size() == nq) {
        sCount++;
        if (!first) {
            for (int aux : sol) {
                out << aux << ' ';
            }
            out << '\n';
            first = true;
        }
        return;
    }

    int line(sol.size() + 1);

    bool ok;
    for (int col(1); col <= nq; col++) {
        ok = true;
        for (int i(0); i < sol.size(); i++) {
            if (col == sol[i] || (col - line) == (sol[i] - (i + 1)) || (col + line) == (sol[i] + (i + 1))) {
                ok = false;
            }
        }
        if (ok) {
            sol.push_back(col);
            queens(nq, sCount, sol, first, out);
            sol.pop_back();
        }
    }

}

int main() {
    std::ifstream fileIn("damesah.in");
    std::ofstream fileOut("damesah.out");

    int nQueens, sCount(0);
    bool first(false);
    std::vector<int> sol;

    fileIn >> nQueens;

    queens(nQueens, sCount, sol, first, fileOut);

    fileOut << sCount;

    fileIn.close();
    fileOut.close();
    return 0;
}