#include <stdio.h>
#include <stdlib.h>
int n, nr = 0, sw = 0;
int a[13];

int verifica(int j)
{
    int i;
    for(i = 1; i < j; i++)
        if(a[i] == a[j]) return 0;
    for(i = 1; i < j; i++)
        if(abs(i - j) == abs(a[i] - a[j])) return 0;
    return 1;
}

void bkt(int j, FILE **write)
{
    int i;
    for(i = 1; i <= n; i++)
    {
        a[j] = i;
        if(verifica(j))
            if(j == n)
            {
                if (sw == 0)
                {
                    for(int k = 1; k <= n; k++)
                        fprintf(*write, "%d ", a[k]);
                    fprintf(*write,"\n");
                    sw = 1;
                }
                nr++;
            }
        else bkt(j+1, write);
    }
}

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

    fscanf(read, "%d", &n);
    bkt(1, &write);
    fprintf(write, "%d", nr);

    fclose(read);
    fclose(write);
    return 0;
}