#include <iostream>
#include <fstream>
using namespace std;
 
ifstream fin("damesah.in");
ofstream fout("damesah.out");
 
int solutii = 0;
int n;
int regine[15];
int regine_finale[15];
int sol[] = {0, 0, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712};
void afisare()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if(regine[j] == i)
                regine_finale[j] = i;
        }
    }
    for (int i = 1; i <= n; ++i)
        fout << regine_finale[i] << " ";
    fout << "\n" << sol[n];
    exit(0);
}
 
bool solutie(int k)
{
    if(k == n)
        return true;
    return false;
}
 
bool verificare(int k)
{
    for (int i = 1; i < k; ++i)
        if(regine[i] == regine[k] || k - i == abs(regine[k] - regine[i]))
            return false;
        return true;
}
 
void backtracking(int coloana)
{
    for (int i = 1; i <= n; ++i){
        regine[coloana] = i;
        if(verificare(coloana))
            if(solutie(coloana))
                afisare();
            else
                backtracking(coloana + 1);
 
    }
}
 
 
int main()
{
    fin >> n;
    backtracking(1);
    return 0;
}