#include<cstdio>
#define MAX_N 13
using namespace std;

int log(unsigned x)
{
    return 31 - __builtin_clz(x);
}

int s[MAX_N+1], nrsol, n;
unsigned col, diag, antidiag;
FILE *fout = fopen("damesah.out","w");

void backtracking(int k)
{
    if(k == n)
    {
        if(++nrsol == 1)
        {
            for(int i=0; i<n; i++)
                fprintf(fout,"%d ",1+log(s[i]));
            fprintf(fout,"\n");
        }
    }
    else
    {
        unsigned mask = col & (antidiag >> k) & (diag >> (n - k - 1));
        while(mask)
        {
            int last = mask & (-(signed)mask);
            s[k] = last;
            col ^= last;
            antidiag ^= last << k;
            diag ^= last << (n- k - 1);
            backtracking(k+1);
            col ^= last;
            antidiag ^= last << k;
            diag ^= last << (n- k - 1);
            mask ^= last;
        }
    }
}

int main()
{
    FILE *fin = fopen("damesah.in","r");
    fscanf(fin,"%d",&n);
    diag = antidiag = (1 << (2*n - 1)) - 1;
    col = (1 << n) - 1;
    backtracking(0);
    fprintf(fout,"%d\n",nrsol);
    fclose(fin);
    fclose(fout);
    return 0;
}