#include <stdio.h>
#define MAXN 20
using namespace std;

int n, col[MAXN], nrsol;
bool uzcol[MAXN], diag1[2 * MAXN], diag2[2 * MAXN];
bool firstSol = 1;

void bkt(int line) {
    if(line > n) {
        if(firstSol) {
            firstSol = 0;
            for(int i = 1; i <= n; i++)
                printf("%d ", col[i]);
            printf("\n");
        }
        ++nrsol;
    }
    for(int j = 1; j <= n; j++)
        if(!uzcol[j] && !diag1[line - j + n] && !diag2[line + j]) {
            col[line] = j;
            uzcol[j] = diag1[line - j + n] = diag2[line + j] = 1;
            bkt(line + 1);
            uzcol[j] = diag1[line - j + n] = diag2[line + j] = 0;
        }
}

int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    scanf("%d", &n);
    bkt(1);
    printf("%d\n", nrsol);

    return 0;
}