#include <bits/stdc++.h>

using namespace std;
int n, ans1;
int r[15], c[15], d[15], anss[15], aux[15];
char a[15][15];
pair <int, int> last[15];
bool check(int i, int j)
{
    for(int jj = 1; jj <= n; ++jj) if(a[i][jj] == '*' && jj != j) return 0;
    for(int ii = 1; ii <= n; ++ii) if(a[ii][j] == '*' && ii != i) return 0;
    int ii = i, jj = j;
    while(ii <= n && jj <= n) {
        ++ii, ++jj;
        if(a[ii][jj] == '*') return 0;
    }
    ii = i, jj = j;
    while(ii >= 1 && jj <= n) {
        --ii, ++jj;
        if(a[ii][jj] == '*') return 0;
    }
    ii = i, jj = j;
    while(ii <= n && jj >= 1) {
        ++ii, --jj;
        if(a[ii][jj] == '*') return 0;
    }
    ii = i, jj = j;
    while(ii >= 1 && jj >= 1) {
        --ii, --jj;
        if(a[ii][jj] == '*') return 0;
    }
    return 1;
}
void solve(int k, int col)
{
    if(k == n + 1) {
        ++ans1;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j) if(a[i][j] == '*') aux[i] = j;
        for(int i = 1; i <= n; ++i) {
                if(anss[i] > aux[i]) {
                    for(int j = 1; j <= n; ++j) anss[j] = aux[j];
                    break;
                }
                else if(anss[i] < aux[i]) break;
        }
    }
    else if(col <= n) {
            for(int i = 1; i <= n; ++i) {
                if(check(i, col)) {
                        r[i] = 1, c[col] = 1, d[abs((n - i + 1) - col)] = 1, a[i][col] = '*', solve(k + 1, col + 1);
                        a[i][col] = '-';
                }
            }
    }
}
int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) anss[i] = 15;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) a[i][j] = '-';
    solve(1, 1);
    for(int i = 1; i <= n; ++i) printf("%d ", anss[i]);
    printf("\n");
    printf("%d", ans1);
    return 0;
}