#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

const int maxQueens = 15;
int* pos;
int boardSize;
int solutions = 0;

ifstream in("./damesah.in");
ofstream out("./damesah.out");

bool position_valid(int k) {
    for (int i = 0; i < k; i++) {
        if (pos[i] == pos[k] || (k - i) == abs(pos[i] - pos[k])) {
            return false;
        }
    }
    return true;
}

void print_solution() {
    for (int i = 0; i < boardSize; i++) {
        out << pos[i] + 1 << " ";
    }
    out << "\n";
}

void place_queen(int k) {
    if (k == boardSize) {
        if (solutions == 0) {
            print_solution();
        }
        solutions += 1;
        return;
    }

    for (int i = 0; i < boardSize; i++) {
        pos[k] = i;
        if (position_valid(k)) {
            place_queen(k+1);
        }
    } 
}

int main(void) {
    in >> boardSize;
    pos = new int[boardSize];
    place_queen(0);
    out << solutions << "\n";
    return 0;
}