#include <iostream>
#include <fstream>
#define pii pair <int, int>
#define x first
#define y second

using namespace std;

int N;
bool a[16][16];
int st[16];
int nr;
int ans[16];

bool OK(const int & x, const int & y)
{
    return 0 < x && x <= N && 0 < y && y <= N;
}

bool Verif(const int & x, const int & y)
{
    for (int i = x - 1; i > 0; -- i)
        if (a[i][y] == 1)
            return false;
    for (int i = x + 1; i <= N; ++ i)
        if (a[i][y] == 1)
            return false;
    for (int i = y - 1; i > 0; -- i)
        if (a[x][i] == 1)
            return false;
    for (int i = y + 1; i <= N; ++ i)
        if (a[x][i] == 1)
            return false;
    for (int i = x, j = y; OK(i, j); ++i, ++j)
        if (!(i == x && j == y) && a[i][j] == 1)
            return false;
    for (int i = x, j = y; OK(i, j); ++i, --j)
        if (!(i == x && j == y) && a[i][j] == 1)
            return false;
    for (int i = x, j = y; OK(i, j); --i, ++j)
        if (!(i == x && j == y) && a[i][j] == 1)
            return false;
    for (int i = x, j = y; OK(i, j); --i, --j)
        if (!(i == x && j == y) && a[i][j] == 1)
            return false;
    return true;
}

void back(int k)
{
    if (k == N + 1)
    {
        ++nr;
        bool ok = false;
        for (int i = 1; i <= N; ++ i)
            if (st[i] < ans[i])
            {
                ok = true;
                break;
            }
            else if (st[i] > ans[i])
                break;
        if (ok)
            for (int i = 1; i <= N; ++ i)
                ans[i] = st[i];
        return ;
    }
    for (int i = 1; i <= N; ++ i)
    {
        st[k] = i;
        a[k][i] = true;
        if (Verif(k, i))
        {
            back(k+1);
        }
        a[k][i] = false;
    }
}

int main()
{
    ifstream f("damesah.in");
    f >> N;
    f.close();
    for (int i = 1; i <= N; ++ i)
        ans[i] = N;
    back(1);
    ofstream g("damesah.out");
    for (int i = 1; i <= N; ++ i)
        g << ans[i] << " " ;
    g << "\n" << nr << "\n";
    g.close();
    return 0;
}