#include <bits/stdc++.h>
using namespace std;

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

int n, ansCounter;
int fr[14][14];

vector<int> ans, minAns(14, 14);

void modifyFr(int line, int col, int modifier) {
    fr[line][col] += modifier;
    for (int i = 1; i <= n; ++i) {
        if (i != line) {
            fr[i][col] += modifier;
        }
    }
    for (int j = 1; j <= n; ++j) {
        if (j != col) {
            fr[line][j] += modifier;
        }
    }
    for (int i = line - 1, j = col - 1; i >= 1 && j >= 1; --i, --j) {
        fr[i][j] += modifier;
    }
    for (int i = line + 1, j = col - 1; i <= n && j >= 1; ++i, --j) {
        fr[i][j] += modifier;
    }
    for (int i = line + 1, j = col + 1; i <= n && j <= n; ++i, ++j) {
        fr[i][j] += modifier;
    }
    for (int i = line - 1, j = col + 1; i >= 1 && j <= n; --i, ++j) {
        fr[i][j] += modifier;
    }
}

void gen(int line) {
    if (line == n + 1) {
        ++ansCounter;
        minAns = min(minAns, ans);
        return;
    }
    for (int col = 1; col <= n; ++col) {
        if (fr[line][col] == 0) {
            modifyFr(line, col, 1);
            ans.push_back(col);
            gen(line + 1);
            ans.pop_back();
            modifyFr(line, col, -1);
        }
    }
}

int main() {
    fin >> n;
    gen(1);
    for (int i = 0; i < n; ++i) {
        fout << minAns[i] << ' ';
    }
    fout << '\n' << ansCounter;
    return 0;
}