#include <stdio.h>
#include <stdbool.h>
#include <math.h>

#define N 13

void printConfiguration(int solutions[N], int size, FILE* fout)
{
    for(int i = 0; i < size; i++)
    {
        // +1 because the we are dealing with 0-based indexed values
        fprintf(fout, "%d ", solutions[i] + 1);
    }
    fprintf(fout, "\n");
}

bool isValid(int solutions[N], int row, int column)
{
    for(int i = 0; i < row; i++)
    {
        if(solutions[i] == column
            || fabs(solutions[i] - column) == fabs(row - i))
        {
            return false;
        }
    }

    return true;
}

void getQueens(int row, int size, int solutions[N], int* solutionCounter,
    FILE* fout)
{
    if(row == size)
    {
        (*solutionCounter)++;
        if(*solutionCounter == 1)
        {
            printConfiguration(solutions, size, fout);
        }

        return;
    }

    for(int i = 0; i < size; i++)
    {
        if(isValid(solutions, row, i))
        {
            solutions[row] = i;
            getQueens(row + 1, size, solutions, solutionCounter, fout);
            solutions[row] = 0;
        }
    }
}

int main(void)
{

    FILE* fin  = fopen("damesah.in", "r");
    FILE* fout = fopen("damesah.out", "w");

    int size;
    int solutionCounter = 0;
    int solutions[N];

    for(int i = 0; i < 13; i++)
        solutions[i] = 0;

    fscanf(fin, "%d", &size);

    getQueens(0, size, solutions, &solutionCounter, fout);
    fprintf(fout, "%d\n", solutionCounter);

    fclose(fin);
    fclose(fout);

    return 0;
}