#include <cstdint>
#include <vector>
#include <cstdio>
#include <cstdlib>

bool findSuccessor(std::vector<int16_t> *stack, uint16_t tableSize) {
    if (stack->back() == tableSize ) return false;
    stack->back()++;
    return true;
}

bool validate(std::vector<int16_t> stack) {
    for (uint32_t i = 0; i < stack.size() - 1; i++) {
        if (stack.back() == stack[i] ||
            abs(i - (stack.size() - 1)) == abs(stack[i] - stack.back())) {
            return false;
        }
    }
    return true;
}

void init(std::vector<int16_t> *stack) {
    stack->push_back(0);
}

bool isSolution(std::vector<int16_t> stack, uint32_t tableSize) {
    return stack.size() == tableSize;
}

void handleSolution(std::vector<int16_t> stack, FILE * fisier) {
    for (int16_t index : stack) {
        fprintf(fisier, "%hd ", index);
    }
    printf("\n");
}

int main() {
    uint16_t tableSize;
    int k = 0;
    FILE * fisier_out = fopen("damesah.out", "w");
    FILE * fisier_in = fopen("damesah.in", "r");

    fscanf(fisier_in, "%hu", &tableSize);

    std::vector<int16_t> stack;
    init(&stack);

    while (!stack.empty()) {
        bool hasSuccessor;
        bool isValid;
        do {
            hasSuccessor = findSuccessor(&stack, tableSize);
            if (hasSuccessor) isValid = validate(stack);
            else isValid = false;
        } while (hasSuccessor && !isValid);

        if (isValid) {
            if (isSolution(stack, tableSize)) {
                if(k > 0){
                    k = k + 1;
                    continue;
                }
                handleSolution(stack, fisier_out);
                k = k + 1;
            } else {
                init(&stack);
            }
        } else {
            stack.pop_back();
        }
    }
    fprintf(fisier_out, "\n%d", k);

    return 0;
}