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

int valid(int st[], int vf) {
    int diff_col, diff_lin;
    int i;

    for (i = 0; i < vf; i++) {
        diff_lin = vf - i;
        diff_col = abs(st[vf] - st[i]);
        if (st[vf] == st[i] || diff_lin == diff_col)
            return 0;
    }

    return 1;
}

int solutie(int n, int poz) {
    return n == poz;
}

void afisare(int n, int st[], FILE* g, int* nr) {
    if (nr == 0) {
        for (int i = 0; i < n; i++)
            fprintf(g, "%d ", st[i] + 1);
        fprintf(g, "\n");
    }
}

void back(int n, int st[], int vf, int* nr, FILE* g) {
    if (solutie(n, vf)) {
        afisare(n, st, g, *nr);
        (*nr)++;
        return;
    }

    for (int i = 0; i < n; i++) {
        st[vf] = i;
        if (valid(st, vf)) {
            back(n, st, vf + 1, nr, g);
        }
    }
}

int main() {
    int n, st[100], nr = 0;
    FILE* f = fopen("grader_test1.in", "r");
    FILE* g = fopen("damesah.out", "w");

    if (f == NULL) {
        printf("NU S-A PUTUT DESCHIDE FISIERUL damesah.in\n");
        exit(0);
    }

    if (g == NULL) {
        printf("NU S-A PUTUT DESCHIDE FISIERUL damesah.out\n");
        fclose(f);
        exit(0);
    }

    fscanf(f, "%d", &n);
    fclose(f);

    back(n, st, 0, &nr, g);

    fprintf(g, "%d", nr);
    fclose(g);

    return 0;
}