/**
Diagonale:
    1 2 3 4
    -------
1 | 4 3 2 1
2 | 5 4 3 2
3 | 6 5 4 3
4 | 7 6 5 4
Antidiagonale:
    1 2 3 4
    -------
1 | 1 2 3 4
2 | 2 3 4 5
3 | 3 4 5 6
4 | 4 5 6 7
 **/
#include <stdio.h>

#define MAX_N 13

FILE *f;

int n;
char s[MAX_N];
char col[MAX_N];
char diag[2 * MAX_N];
char anti[2 * MAX_N];
int numSol;

void placeQueen(int q) {
  if (q == n) {
      if (++numSol <= 1) {
        for (int i = 0; i < n; i++) {
          fprintf(f, "%d ", 1 + s[i]);
        }
        fputc('\n', f);
      }
  } else {
    for (int i = 0; i < n; i++) {
      if (!col[i] && !diag[q + n - 1 - i] && !anti[q + i]) {
          s[q] = i;
          col[i] = diag[q + n - 1 - i] = anti[q + i] = 1;
          placeQueen(q + 1);
          col[i] = diag[q + n - 1 - i] = anti[q + i] = 0;
      }
    }
  }
}

int main(void) {
  f = fopen("damesah.in", "r");
  fscanf(f, "%d", &n);
  fclose(f);

  f = fopen("damesah.out", "w");
  placeQueen(0);
  fprintf(f, "%d\n", numSol);
  fclose(f);
  return 0;
}