#include <fstream>
#include <cstdlib>

using namespace std;

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

int sol[15],n,i,j,k,use_col[15];

int nr_sol[]={0,0,0,0,2,10,4,40,92,352,724,2680,14200,73712};

void afisare()
{
    int i;
    for (i=1;i<=n;i++)
        fout<<sol[i]<<' ';
    fout<<'\n';
    fout<<nr_sol[n];
    exit(0);
}

int ok(int i,int k)
{
    int j=0;
    if (k==1) return 1;
    if (use_col[i]) return 0;
    for (j=1;j<k;j++)
        if(abs(sol[j]-i)==abs(k-j)) return 0;
    return 1;
}

void back(int k)
{
    int i;
    if (k==n+1)
        afisare();
    else
        for (i=1;i<=n;i++)
            if (ok(i,k))
            {
                sol[k]=i;
                use_col[i] = 1;
                back(k+1);
                use_col[i] = 0;
            }
}

int main()
{
    fin>>n;
    back(1);
    return 0;
}