#include <stdio.h>

#define MAX 100

int usedMainDiagonal[MAX];
int usedSecondaryDiagonal[MAX];
int usedColumns[MAX];
int solution[MAX];
int n = 0;
int count = 0;
int firstSolution = 1;
FILE* fin; FILE* fout;

inline __attribute__((always_inline)) int isValid(int r, int c) {
	if(usedColumns[c] || usedMainDiagonal[r-c+n] || usedSecondaryDiagonal[r+c]) {
		return 0;
	} else { return 1; }
} 

inline __attribute__((always_inline)) void placeQueen(int r, int c) {
	solution[r] = c;
	usedColumns[c] = 1;
	usedMainDiagonal[r-c+n] = 1;
	usedSecondaryDiagonal[r+c] = 1;
	return;
}

inline __attribute__((always_inline)) void removeQueen(int r, int c) {
	usedColumns[c] = 0;
	usedMainDiagonal[r-c+n] = 0;
	usedSecondaryDiagonal[r+c] = 0;
	return;
}

inline __attribute__((always_inline)) void printSolution() {
	for(int i = 0; i < n; i++) {
		fprintf(fout, "%d ", solution[i]+1);
	}
	fprintf(fout, "\n");	
	return;
}

void solve(int r) {
	if(r == n) {count++; if(firstSolution) { printSolution(); firstSolution = 0; }return;}

	for(int c = 0; c < n; c++) {
		if(isValid(r, c)) {
			placeQueen(r, c);
			solve(r+1);
			removeQueen(r, c);
		}
	}  	
}

int main() {
	fin = fopen("damesah.in", "r");
	fout = fopen("damesah.out", "w");

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

	solve(0);

	fprintf(fout, "%d\n", count);

	fclose(fin);
	fclose(fout);
}