#include <cstdio>

using namespace std;

const int MAX_N = 13;

FILE *in, *out;

bool col[MAX_N], diag1[2*MAX_N], diag2[2*MAX_N];
bool gasit;

int sol[MAX_N];

int n;
int nrsol;

void afis()
{
    for(int i = 0; i < n; i++)
        fprintf(out, "%d ", sol[i]+1);
    fprintf(out, "\n");
}

void bkt(int p)
{
    if(p == n)
    {
        if(!gasit)
        {
            gasit = true;
            afis();
        } else {
            nrsol++;
        }
    } else {
        for(int i = 0; i < n; i++)
        {
            sol[p] = i;
            if(!col[i] && !diag1[i-p+n-1] && !diag2[i+p])
            {
                col[i] = diag1[i-p+n-1] = diag2[i+p] = true;
                bkt(p+1);
                col[i] = diag1[i-p+n-1] = diag2[i+p] = false;
            }
        }
    }
}

int main()
{
    in = fopen("damesah.in", "r");
    out = fopen("damesah.out", "w");

    fscanf(in, "%d", &n);

    bkt(0);

    fprintf(out, "%d", nrsol);

    fclose(in);
    fclose(out);
    return 0;
}